Khai phá motif cho đa chuỗi thời gian và phát hiện bất thường bằng các phương pháp học máy
- 77 trang
- file .pdf
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
LUẬN VĂN THẠC SĨ
Khai phá motif cho đa chuỗi thời gian
và phát hiện bất thường bằng các
phương pháp học máy
PHẠM NGỌC QUANG ANH
[email protected]
Chuyên ngành: Toán Tin
Giảng viên hướng dẫn: TS. Nguyễn Thị Ngọc Anh Chữ ký của GVHD
Viện: Toán ứng dụng và Tin học
HÀ NỘI, 10/2022
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn : Phạm Ngọc Quang Anh
Đề tài luận văn: Khai phá motif cho đa chuỗi thời gian và phát hiện bất
thường bằng các phương pháp học máy
Chuyên ngành: Toán tin
Mã số SV: 20202959M
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn
xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng
ngày 31/10/2022 với các nội dung sau:
● Bổ sung thêm phần lời mở đầu.
● Chỉnh sửa lỗi soạn thảo, câu chữ tại các trang 11, 14, 15, 18, 23, 29.
● Chỉnh sửa lại hình mô hình tổng quan 2.1 trang 19.
Ngày 31 tháng 10 năm 2022
Giáo viên hướng dẫn Tác giả luận văn
CHỦ TỊCH HỘI ĐỒNG
ĐỀ TÀI LUẬN VĂN
Tên học viên: Phạm Ngọc Quang Anh
Mã học viên: 20202959M
Tên đề tài: Khai phá motif cho đa chuỗi thời gian và phát hiện bất
thường bằng các phương pháp học máy
Mã đề tài: 2020BTOANTIN-KH14
Hệ : Thạc sĩ khoa học
Ngành: Toán Tin
Cán bộ hướng dẫn: TS. Nguyễn Thị Ngọc Anh
Đơn vị: Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa
Hà Nội
Chữ ký của GVHD
Lời cảm ơn
Trước khi đi vào nội dung luận văn, em xin có lời cảm ơn chân thành đến TS.
Nguyễn Thị Ngọc Anh đã trợ giúp và tận tình hướng dẫn em hoàn thành tốt
luận văn này. Em cũng xin gừi những lời cảm ơn đến các thầy cô Viện Toán ứng
dụng và Tin học, trường Đại học Bách khoa Hà Nội đã giảng dạy những kiến
thức bổ ích cho em trong suốt quá trình học tập cao học.
Ngoài ra, em cũng gửi lời cảm ơn tới đồng nghiệp và ban lãnh đạo Viện Nghiên
cứu Ứng dụng công nghệ CMC đã hỗ trợ và tạo điều kiện thuận lợi cho em để
hoàn thiện luận văn, đặc biệt là anh Hoàng Văn Đông đã giúp đỡ em rất nhiều
trong quá trình thực hiện luận văn.
Cuối cùng, em xin gửi lời cảm ơn đến tất cả các thành viên trong gia đình em
đã quan tâm và tạo động lực cố gắng để em hoàn thành luận văn này.
Hà Nội, ngày 24 tháng 10 năm 2022
Học viên thực hiện
Phạm Ngọc Quang Anh
1
Mục lục
Danh mục ký hiệu, chữ viết tắt 4
Danh sách hình vẽ 6
Danh sách bảng 7
Danh sách thuật toán 8
Mở đầu 9
1 Giới thiệu chung 12
1.1 Bài toán phát hiện bất thường . . . . . . . . . . . . . . . . . . . . . 12
1.1.1 Nguồn dữ liệu đầu vào . . . . . . . . . . . . . . . . . . . . . 12
1.1.2 Các loại bất thường . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Nhãn dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.4 Đầu ra của bài toán . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Bài toán phân lớp và một số thuật toán học máy . . . . . . . . . . 14
1.2.1 Bài toán phân lớp . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Một số thuật toán học máy . . . . . . . . . . . . . . . . . . 15
2 Xây dựng mô hình khai phá motif cho chuỗi thời gian và phát
hiện bất thường 17
2.1 Mô hình tổng quan . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Mô hình hóa dữ liệu thành chuỗi thời gian . . . . . . . . . . . . . . 19
2.3 Khai phá motif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 Xây dựng chuỗi ký hiệu . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Tìm kiếm motif bất thường . . . . . . . . . . . . . . . . . . 25
2.4 Xây dựng bộ thuộc tính bất thường và phân lớp . . . . . . . . . . 28
2.5 Đánh giá kết quả phân lớp . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 Ma trận nghi ngờ . . . . . . . . . . . . . . . . . . . . . . . . 31
2
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
2.5.2 Precision và Recall . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.3 Độ đo F1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Ứng dụng mô hình phát hiện bất thường vào dữ liệu hoạt động
mua hàng 33
3.1 Mô tả bộ dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Mô hình hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Tài liệu tham khảo 46
Phụ lục 50
A Công bố khoa học liên quan 51
3
Danh mục ký hiệu, chữ viết tắt
T tập mốc thời gian
O tập các đối tượng
D tập dữ liệu giao dịch của các đối tượng
TS tập chuỗi thời gian
Z phép trừ của chuỗi thời gian
SB tập chuỗi ký hiệu
S tập các chuỗi con của chuỗi ký hiệu
A tập chuỗi ký hiệu giao dịch của các đối tượng gian lận
R ngưỡng tương đồng
P tập motif hành vi
F tập thuộc tính
KN N K-nearest neighbor (K láng giềng gần nhất)
SAX Symbolic Aggregate approXimation
DT W Dynamic Time Warping
score Chỉ số chọn mẫu
TP True Positive
FP False Positive
TN True Negative
.
4
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
FN False Negative
P re Precision
Rec Recall
F1 độ đo F1
5
Danh sách hình vẽ
2.1 Sơ đồ tổng quan của mô hình phân tích hành vi trên chuỗi thời
gian. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Mô tả chuỗi thời gian đơn giản: (a) Chuỗi thời gian. (b) Phép trừ
chuỗi của chuỗi thời gian. . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Các hành vi của đối tượng được mô tả dựa trên chuỗi thời gian
đơn giản. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Quy trình khai phá motif. . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Chuyển đổi phép trừ chuỗi của chuỗi thời gian đơn giản thành
chuỗi ký hiệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Tính toán giá trị thuộc tính. . . . . . . . . . . . . . . . . . . . . . . 29
2.7 Minh họa một ma trận nghi ngờ. . . . . . . . . . . . . . . . . . . . 31
3.1 Dữ liệu hoạt động mua hàng. . . . . . . . . . . . . . . . . . . . . . 34
3.2 Chuỗi thời gian thể hiện hành vi thay đổi địa điểm mua hàng của
khách hàng trong 3 năm. . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Chuyển đổi chuỗi thời gian hành vi của từng khách hàng thành
chuỗi ký hiệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Biểu đồ hộp đánh giá kết quả phân lớp từ hành vi thay đổi địa
điểm theo từng thuật toán. . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Biểu đồ hộp đánh giá kết quả phân lớp từ hành vi thay đổi hàng
hóa mua theo từng thuật toán. . . . . . . . . . . . . . . . . . . . . 41
3.6 Biểu đồ hộp đánh giá kết quả phân lớp từ hành vi thay đổi cả địa
điểm và hàng hóa mua theo từng thuật toán. . . . . . . . . . . . . 42
6
Danh sách bảng
2.1 Minh họa ma trận khoảng cách với 5 chuỗi ký hiệu . . . . . . . . . 26
2.2 Ma trận khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Tìm kiếm chuỗi trung tâm motif . . . . . . . . . . . . . . . . . . . 27
3.1 Mô tả dữ liệu hoạt động mua hàng . . . . . . . . . . . . . . . . . . 33
3.2 motif hành vi đáng nghi với R = 0.75 . . . . . . . . . . . . . . . . . 38
3.3 Kết quả phát hiện bất thường dựa trên hành vi thay đổi địa điểm 39
3.4 Kết quả phát hiện bất thường dựa trên hành vi thay đổi hàng hóa
mua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Kết quả phát hiện bất thường dựa trên hành vi thay đổi cả địa
điểm và hàng hóa mua . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Thời gian chạy trung bình của từng thuật toán . . . . . . . . . . . 42
3.7 Kịch bản 4: Kết quả phát hiện bất thường dựa trên việc tổng hợp
điểm đánh giá từ thuật toán Random Forest . . . . . . . . . . . . 43
3.8 Kịch bản 5: Kết quả phát hiện bất thường dựa trên việc tổng hợp
điểm đánh giá từ các thuật toán học máy. . . . . . . . . . . . . . . 43
3.9 Thời gian chạy trung bình của kịch bản 4 và 5 . . . . . . . . . . . 43
7
Danh sách thuật toán
1 Thuật toán khai phá motif trên chuỗi thời gian. . . . . . . . 28
2 Thuật toán phân lớp đối tượng. . . . . . . . . . . . . . . . . . . 30
8
Mở đầu
Lý do chọn đề tài
Phát hiện bất thường là một chủ đề quan trọng và đã được nghiên cứu trong
rất nhiều lĩnh vực [10] tiêu biểu như phát hiện các cuộc tấn công đánh cắp dữ
liệu trong an ninh mạng [27][37] hay cảnh báo lỗi trong các hệ thống giám sát,
cảm biến [36]. Đối với lĩnh vực kinh tế nói chung, bài toán phát hiện bất thường
phổ biến là phát hiện gian lận trong các hoạt động tài chính. Phát hiện gian lận
là một bài toán cấp thiết của nhiều công ty, tổ chức như ngân hàng, bảo hiểm,
các cơ quan nhà nước [28]. Vì vậy, phát hiện gian lận tài chính được rất nhiều
các chuyên gia và nhà nghiên cứu quan tâm và thực hiện hàng loạt công trình
nghiên cứu trong nhiều năm gần đây [4][22][28][32][41].
Cùng với sự phát triển của thời đại công nghệ số hiện nay, các giao dịch tài
chính bùng nổ với một lượng dữ liệu khổng lồ bởi sự phát triển của các hình
thức giao dịch qua mạng và di động. Các hình thức giao dịch này có chi phí thấp
và rất nhanh chóng, tiện lợi. Từ sự phát triển này, việc xử lý giao dịch từ hàng
triệu giao dịch với vô số loại hành vi khác nhau không còn hiệu quả với phương
thức xử lý thủ công. Do đó, yêu cầu đặt ra là cần xây dựng một hệ thống thời
gian thực trích rút được các thông tin thể hiện những hành vi bất thường trong
quá trình hoạt động của đối tượng xấu và sử dụng được các thông tin này để so
khớp, đối chiếu xác định các đối tượng có dấu hiệu nghi vấn gian lận.
Các công trình nghiên cứu liên quan
Dữ liệu chuỗi thời gian được sử dụng rộng rãi để mô tả quá trình hoạt động của
đối tượng và phân tích các bất thường ẩn giấu bên trong [12][19][32][38][44]. Một
cách tiếp cận trong việc phân tích chuỗi thời gian là sử dụng các biểu diễn rời
rạc, với ví dụ tiêu biểu là thuật toán SAX (Symbolic Aggregate approXimation)
và các cải tiến của nó [2][13][33][42][43].
9
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
Khi các chuyên gia phân tích đánh giá rủi ro một đối tượng nào đó, một trong
những cách họ thường sử dụng là xem xét quá trình hoạt động của đối tượng
này trong quá khứ. Họ tổng kết những kinh nghiệm có được từ những đối tượng
gian lận, sử dụng những kinh nghiệm này để đối chiếu với đối tượng đang được
xét và phân tích xem liệu các hành vi của đối tượng này có giống với những hành
vi đáng ngờ hay không. Trong phân tích chuỗi thời gian, các độ đo khoảng cách
được sử dụng để tính toán sự tương đồng giữa các chuỗi mô tả hành vi. Độ đo
DTW (Dynamic Time Warping) thường được sử dụng vì tính linh hoạt trong
việc so khớp chuỗi thời gian [14][17][20][23][25].
Nhiều ứng dụng trí tuệ nhân tạo và khai phá dữ liệu được áp dụng để phát
hiện các yếu tố bất thường ẩn giấu trong dữ liệu [1][11][16][26]. Phân tích xâm
nhập mạng sử dụng KNN [36], AdaBoost [27][37], hồi quy logistic [30] để xác
định các sự kiến bất thường là nguy cơ của các cuộc tấn công mạng. Vorobyev
sử dụng các thuật toán thuộc lớp thuật toán cây quyết định [40] để giảm thiểu
các kết quả phát hiện nhầm trong hệ thống chống gian lận của ngân hàng. Các
gian lận trong giao dịch thẻ tín dụng được đánh giá dựa trên nhiều thuật toán
học máy để đưa ra kết quả tối ưu [5][26].
Mục đích nghiên cứu
Mục tiêu chính của luận văn là trình bày một mô hình áp dụng trong lĩnh vực
phát hiện gian lận giao dịch tài chính. Cụ thể, mô hình đề xuất giải quyết các
vấn đề sau
• Xây dựng thuật toán khai phá motif đưa ra các motif hành vi, thói quen
bất thường mà những đối tượng gian lận sử dụng.
• Phân lớp các đối tượng nhằm xác định nhóm đối tượng có hành vi bất
thường.
• Tận dụng kết quả đánh giá trên từng hành vi để cải thiện kết quả phân lớp
chính xác hơn.
Đối tượng và phạm vi nghiên cứu
Trong khuôn khổ luận văn, tác giả tiếp cận và phân tích những vấn đề của bài
toán phát hiện bất thường trong giao dịch tài chính thông qua sự kết hợp của
phương pháp khai phá motif trong lý thuyết nhận dạng và phát hiện bất thường
10
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
bằng các thuật toán học máy. Có nhiều loại hình giao dịch tài chính như giao dịch
vay nợ, thế chấp, giao dịch tài khoản, giao dịch qua thẻ tín dụng trong đó phổ
biến nhất là giao dịch mua bán hàng hóa trực tiếp. Mô hình đề xuất được áp dụng
cụ thể vào hoạt động mua bán hàng hóa của khách hàng với doanh nghiệp bán lẻ.
Dữ liệu trong giao dịch mua bán hàng hóa bao gồm các thông tin về người
mua; thông tin về hàng hóa như loại hình hàng hóa, giá thành; thông tin giao
dịch như địa điểm giao dịch, tổng chi phí giao dịch, thời gian giao dich. Luận
văn tập trung phân tích hành vi thay đổi địa điểm và loại hàng hóa mua của
khách hàng trong thời gian ba năm từ năm 2015 đến năm 2017.
Cấu trúc luận văn và các đóng góp của tác giả
Nội dung chính của luận văn được trình bày trong ba chương
• Chương 1: Giới thiệu chung về bài toán phát hiện bất thường và các thuật
toán phân lớp trong học máy.
• Chương 2: Trình bày phương pháp xây dựng mô hình nhận dạng motif trong
tập chuỗi thời gian và sử dụng các thuật toán học máy để phân lớp. Qua
đó, xác định được các đối tượng có hành vi bất thường.
• Chương 3: Áp dụng mô hình đưa ra với dữ liệu hoạt động mua hàng.
Trong luận văn này, đóng góp chính của tác giả là xây dựng được sơ đồ tổng
quan của mô hình phân lớp mới dựa trên việc phân tích các thói quen trong giao
dịch của các đối tượng.
11
Chương 1
Giới thiệu chung
1.1 Bài toán phát hiện bất thường
Phát hiện bất thường là bài toán nhận dạng motif trong dữ liệu mà không phù
hợp với hành vi thông thường. Những motif không phù hợp này thường được gọi
là điểm bất thường, điểm ngoại lai, những quan sát trái ngược, ngoại lệ trong
nhiều ngữ cảnh khác nhau [10].
Phát hiệt bất thường được sử dụng rộng rãi trong nhiều lĩnh vực
• Phát hiện gian lận trong hành vi tiêu dùng thẻ tín dụng, bảo hiểm hay chăm
sóc sức khỏe [4][9][22][28][35].
• Phát hiện xâm nhập trong an ninh mạng [27][36][37].
• Phát hiện lỗi trong các hệ thống an toàn và các hoạt động giám sát [14][31].
Một điểm/tập hợp bất thường được định nghĩa là một motif không phù hợp
với hành vi thông thường. Vì vậy, một cách tiếp cận trực tiếp cho bài toán phát
hiện bất thường, là xác định một vùng đại diện cho các hành vi bình thường và
trích rút bất kỳ quan sát nào không thuộc vùng bình thường này là bất thường
[10].
Một bài toán phát hiện bất thường bao gồm bốn khía cạnh chính: nguồn dữ
liệu đầu vào, các loại bất thường, nhãn của dữ liệu và đầu ra của quy trình phát
hiện bất thường [10].
1.1.1 Nguồn dữ liệu đầu vào
Mỗi điểm dữ liệu đầu vào của bài toán được mô tả dưới dạng tập hợp các
thuộc tính. Các thuộc tính này có nhiều kiểu như nhị phân, các giá trị rời rạc
12
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
hay liên tục. Mỗi điểm dữ liệu có thể gồm chỉ một thuộc tính (đơn biến) hay
nhiều thuộc tính (đa biến).
Ngoài ra, các điểm dữ liệu có thể có liên kết với nhau, chẳng hạn dữ liệu dạng
chuỗi [14][38], dữ liệu dạng đồ thị [29]. Trong dữ liệu dạng chuỗi, các điểm dữ
liệu có tính thứ tự tuyến tính, ví dụ như chuỗi thời gian, chuỗi gen, chuỗi protein.
Trong dữ liệu dạng đồ thị, mỗi điểm dữ liệu được biểu diễn dưới dạng đỉnh của
đồ thị và liên kết với nhau bởi các cạnh.
1.1.2 Các loại bất thường
Đặc trưng của bất thường được chia làm ba loại [10]
Bất thường điểm
Nếu một điểm dữ liệu cụ thể được coi là dị thường với phần còn lại của tập dữ
liệu, điểm dữ liệu đó là một bất thường điểm. Loại bất thường này xuất hiện phổ
biến trong các bài toán phát hiện gian lận thẻ tín dụng. Cụ thể, xét một thuộc
tính số tiền tiêu dùng trong dữ liệu giao dịch thẻ tín dụng của các cá nhân, một
giao dịch có số tiền tiêu dùng ở một thời điểm cao đột biến so với hoạt động tiêu
dùng thông thường của cá nhân đó được coi là một bất thường điểm.
Bất thường ngữ cảnh
Một điểm/tập dữ liệu là bất thường trong một ngữ cảnh cụ thể được gọi là
một bất thường ngữ cảnh. Ngữ cảnh trong tập dữ liệu có thể khoảng thời gian
cụ thể, hay các thông tin phân vùng không gian như độ cao, độ sâu. Trong bài
toán phát hiện gian lận thẻ tín dụng, số tiền tiêu dùng trung bình theo tuần cao
đột biến vào những khung thời gian sự kiện giảm giá hoặc dịp lễ hằng năm sẽ
không được coi là bất thường vì hành vi này khớp với xu hướng chi tiêu chung.
Nhưng việc chi tiêu cùng một số tiền đó vào khoảng thời gian thông thường sẽ
được gọi là bất thường ngữ cảnh.
Bất thường nhóm
Nếu một tập hợp các điểm dữ liệu liên quan có sự khác biệt với toàn bộ tập
dữ liệu thì đây là một bất thường nhóm. Một điểm dữ liệu cụ thể trong loại bất
thường này có thể không phải là bất thường điểm, nhưng sự xuất hiện liên tục
các điểm này dẫn đến bất thường trong tập dữ liệu.
13
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
1.1.3 Nhãn dữ liệu
Nhãn của một điểm dữ liệu xác định xem điểm này là bình thường hay bất
thường. Quá trình thu thập dữ liệu được gán nhãn chính xác là phức tạp. Việc
gán nhãn thường được thực hiện một cách thủ công bởi chuyên gia dẫn đến việc
tốn chi phí về mặt thời gian. Thông thường, việc thu thập tập đã gán nhãn từ dữ
liệu bất thường khó khăn hơn việc lấy nhãn từ dữ liệu bình thường. Phụ thuộc
vào số lượng nhãn của tập dữ liệu, bài toàn phát hiện bất thường có thể được
triển khai theo ba hướng [10]
• Phát hiện bất thường có giám sát: Tập dữ liệu luyện được đánh nhãn đầy
đủ với hai loại là bất thường và bình thường. Cách tiếp cận thông thường
là xây dựng mô hình phù hợp từ dữ liệu luyện sau đó dự đoán nhãn cho các
điểm dữ liệu bất kỳ.
• Phát hiện bất thường bán giám sát: Tập dữ liệu luyện chỉ bao gồm các điểm
được gán nhãn bình thường. Cách tiếp cận với trường hợp này là xây dựng
một mô hình tương ứng với hành vi bình thường, và sử dụng mô hình này
để xác định ra các điểm bất thường trong tập dữ liệu [39].
• Phát hiện bất thường không giám sát: Tập dữ liệu không có nhãn. Các kỹ
thuật cho bài toán này dựa trên giả định ngầm các điểm dữ liệu bình thường
có tần suất xuất hiện nhiều hơn các điểm bất thường trong tập dữ liệu [24].
1.1.4 Đầu ra của bài toán
Đầu ra của bài toán phát hiện bất thường gồm hai loại [10]
• Điểm số bất thường: Điểm dữ liệu đại diện cho hành vi của đối tượng được
tính điểm. Sau đó xác định ra số lượng điểm cụ thể có điểm bất thường cao
nhất hoặc đưa ra một ngưỡng điểm số để chọn các điểm bất thường.
• Nhãn: Các đối tượng bất thường và bình thường được phân biệt qua nhãn.
1.2 Bài toán phân lớp và một số thuật toán học máy
1.2.1 Bài toán phân lớp
Phân lớp là quá trình tìm kiếm một mô hình phân biệt các lớp dữ liệu. Mô
hình được xây dựng dựa trên việc phân tích tập dữ liệu luyện và được sử dụng
để dự đoán nhãn lớp của các đối tượng mà chưa biết thông tin nhãn [21].
14
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
Cụ thể, cho tập nhãn lớp C = {1, 2, . . . , C} và tập điểm dữ liệu X ⊂ Rd , ta tìm
một hàm phân lớp f : Rd → C. Với điểm dữ liệu x ∈ X , y = f (x) sẽ gán điểm dữ
liệu vào lớp có nhãn y .
Ngoài ra, f : Rd → RC cũng là một hàm phân lớp với đầu ra là một vector thể
hiện xác suất điểm dữ liệu được gán nhãn vào từng lớp. Điểm dữ liệu sẽ được
gán vào lớp có xác suất gán nhãn cao nhất.
1.2.2 Một số thuật toán học máy
K-láng giềng gần nhất
Thuật toán K -láng giềng gần nhất (KNN) là một trong những thuật toán học
giám sát đơn giản. Thuật toán hoạt động dựa trên nguyên lý nhãn của đối tượng
được xác định dựa trên các đối tượng lân cận nó [15]. Cụ thể, nhãn của điểm
của điểm dữ liệu có thể được xác định qua việc chọn theo đa số (major voting)
nhãn trong K điểm gần nhất hay đánh trọng số cho mỗi điểm gần nhất rồi đưa
ra kết quả.
KNN được ứng dụng trong việc phát hiện chuỗi trạng thái bất thường trong
hoạt động vệ tinh [14]. Nghiên cứu của Ming-Yang Su [36] cũng sử dụng KNN để
phát hiện nhanh chóng các tình huống tấn công mạng dựa trên lưu lượng mạng
bất thường.
Cây quyết định
Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng
để phân lớp các đối tượng dựa vào tập hợp các luật. Thành phần của cây quyết
định bao gồm các nút biểu diễn cho cấu trúc của nhánh. Có hai loại nút, nút
quyết định được sư dụng để ra quyết định và có nhiều nhánh, nút lá là đầu ra
của nút quyết định và không có nhánh con [6].
Cây quyết định được ứng dụng trong việc phát hiện gian lận tín dụng và
thanh toán của ngân hàng [34][40].
Rừng ngẫu nhiên
Rừng ngẫu nhiên (Random Forest) là thuật toán học kết hợp phát triển từ
thuật toán cây quyết định. Ý tưởng thực hiện của thuật toán là luyện hàng loạt
các cây quyết định trên các tập dữ liệu con của tập luyện sinh nhờ phương pháp
15
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
Bagging [7][8].
Cụ thể, ta chọn ra k tập dữ liệu con từ tập dữ liệu luyện. Ứng với mỗi tập
con này, ta chọn một tập thuộc tính con từ không gian thuộc tính và xây dựng
một cây quyết định phân lớp trên bộ dữ liệu này.
Sau khi xây dựng được k cây quyết định, nhãn của điểm dữ liệu dược xác
định dựa trên việc tổng hợp các kết quả đánh nhãn từ các cây quyết định này và
sử dụng phương pháp bỏ phiếu đa số (majority voting) để đưa ra kết luận nhãn
cuối cùng.
AdaBoost
Được đề xuất bởi Yoav Freund và Robert Schapire [18], AdaBoost (Adaptive
Boosting) thuộc loại thuật toán học kết hợp và phân lớp. Ý tưởng của thuật
toán là kết hợp các bộ phân lớp tồi để xây dựng một bộ phân lớp mạnh có tính
chính xác cao hơn [5].
Hồi quy logistic
Hồi quy logistic là thuật toán học máy phổ biến được sử dụng cho học có giám
sát. Thuật toán ước lượng xác suất phân lớp nhị phân dựa trên một hay nhiều
đặc trưng [5]. Hồi quy logistic sử dụng hàm phi tuyến sigmoid để làm hàm phân
lớp. Cụ thể, với một điểm dữ liệu x ∈ Rd và bộ tham số w = {wi }ni=0
1
f (t) = (1.1)
1 + e−t
n
X
t= wi xi
i=0
16
Chương 2
Xây dựng mô hình khai phá motif
cho chuỗi thời gian và phát hiện bất
thường
Nội dung chương 2 đề cập đến quy trình xây dựng mô hình khai phá motif và
phân lớp đối tượng sử dụng các thuật toán học máy.
Phần 2.1 đề xuất mô hình tổng quan quy trình phân tích và phát hiện bất
thường. Phần 2.2 sẽ mô tả quy trình mô hình hóa dữ liệu thành chuỗi thời gian.
Phần 2.3 sẽ đề cập đến khai phá motif bất thường từ những chuỗi thời gian đã
được mô hình hóa. Phần 2.4 mô tả quá trình xây dựng bộ thuộc tính bất thường
và phân lớp. Cuối cùng, phần 2.5 đưa ra các chỉ số đánh giá kết quả phát hiện
bất thường được sử dụng trong luận văn.
2.1 Mô hình tổng quan
Dữ liệu giao dịch trong kinh tế chứa đựng một lượng lớn thông tin thể hiện
hoạt động của các đối tượng. Để xác định được các kịch bản gian lận được che
giấu trong các hoạt động giao dịch này, ta cần xét một chuỗi các giao dịch liên
tiếp do cùng một đối tượng thực hiện [3].
Định nghĩa 2.1. Một chuỗi giao dịch liên tiếp do đối tượng thực hiện được gọi
là một hành vi.
Yêu cầu đặt ra cho một mô hình phát hiện bất thường là tìm ra các motif của
các hành vi do các đối tượng gian lận thực hiện trước giao dịch phát sinh gian
lận. Các motif bất thường sẽ được sử dụng để tìm kiếm những hành vi giao dịch
17
LUẬN VĂN THẠC SĨ
Khai phá motif cho đa chuỗi thời gian
và phát hiện bất thường bằng các
phương pháp học máy
PHẠM NGỌC QUANG ANH
[email protected]
Chuyên ngành: Toán Tin
Giảng viên hướng dẫn: TS. Nguyễn Thị Ngọc Anh Chữ ký của GVHD
Viện: Toán ứng dụng và Tin học
HÀ NỘI, 10/2022
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc
BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn : Phạm Ngọc Quang Anh
Đề tài luận văn: Khai phá motif cho đa chuỗi thời gian và phát hiện bất
thường bằng các phương pháp học máy
Chuyên ngành: Toán tin
Mã số SV: 20202959M
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn
xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng
ngày 31/10/2022 với các nội dung sau:
● Bổ sung thêm phần lời mở đầu.
● Chỉnh sửa lỗi soạn thảo, câu chữ tại các trang 11, 14, 15, 18, 23, 29.
● Chỉnh sửa lại hình mô hình tổng quan 2.1 trang 19.
Ngày 31 tháng 10 năm 2022
Giáo viên hướng dẫn Tác giả luận văn
CHỦ TỊCH HỘI ĐỒNG
ĐỀ TÀI LUẬN VĂN
Tên học viên: Phạm Ngọc Quang Anh
Mã học viên: 20202959M
Tên đề tài: Khai phá motif cho đa chuỗi thời gian và phát hiện bất
thường bằng các phương pháp học máy
Mã đề tài: 2020BTOANTIN-KH14
Hệ : Thạc sĩ khoa học
Ngành: Toán Tin
Cán bộ hướng dẫn: TS. Nguyễn Thị Ngọc Anh
Đơn vị: Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa
Hà Nội
Chữ ký của GVHD
Lời cảm ơn
Trước khi đi vào nội dung luận văn, em xin có lời cảm ơn chân thành đến TS.
Nguyễn Thị Ngọc Anh đã trợ giúp và tận tình hướng dẫn em hoàn thành tốt
luận văn này. Em cũng xin gừi những lời cảm ơn đến các thầy cô Viện Toán ứng
dụng và Tin học, trường Đại học Bách khoa Hà Nội đã giảng dạy những kiến
thức bổ ích cho em trong suốt quá trình học tập cao học.
Ngoài ra, em cũng gửi lời cảm ơn tới đồng nghiệp và ban lãnh đạo Viện Nghiên
cứu Ứng dụng công nghệ CMC đã hỗ trợ và tạo điều kiện thuận lợi cho em để
hoàn thiện luận văn, đặc biệt là anh Hoàng Văn Đông đã giúp đỡ em rất nhiều
trong quá trình thực hiện luận văn.
Cuối cùng, em xin gửi lời cảm ơn đến tất cả các thành viên trong gia đình em
đã quan tâm và tạo động lực cố gắng để em hoàn thành luận văn này.
Hà Nội, ngày 24 tháng 10 năm 2022
Học viên thực hiện
Phạm Ngọc Quang Anh
1
Mục lục
Danh mục ký hiệu, chữ viết tắt 4
Danh sách hình vẽ 6
Danh sách bảng 7
Danh sách thuật toán 8
Mở đầu 9
1 Giới thiệu chung 12
1.1 Bài toán phát hiện bất thường . . . . . . . . . . . . . . . . . . . . . 12
1.1.1 Nguồn dữ liệu đầu vào . . . . . . . . . . . . . . . . . . . . . 12
1.1.2 Các loại bất thường . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Nhãn dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.4 Đầu ra của bài toán . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Bài toán phân lớp và một số thuật toán học máy . . . . . . . . . . 14
1.2.1 Bài toán phân lớp . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Một số thuật toán học máy . . . . . . . . . . . . . . . . . . 15
2 Xây dựng mô hình khai phá motif cho chuỗi thời gian và phát
hiện bất thường 17
2.1 Mô hình tổng quan . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Mô hình hóa dữ liệu thành chuỗi thời gian . . . . . . . . . . . . . . 19
2.3 Khai phá motif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 Xây dựng chuỗi ký hiệu . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Tìm kiếm motif bất thường . . . . . . . . . . . . . . . . . . 25
2.4 Xây dựng bộ thuộc tính bất thường và phân lớp . . . . . . . . . . 28
2.5 Đánh giá kết quả phân lớp . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 Ma trận nghi ngờ . . . . . . . . . . . . . . . . . . . . . . . . 31
2
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
2.5.2 Precision và Recall . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.3 Độ đo F1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Ứng dụng mô hình phát hiện bất thường vào dữ liệu hoạt động
mua hàng 33
3.1 Mô tả bộ dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Mô hình hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Tài liệu tham khảo 46
Phụ lục 50
A Công bố khoa học liên quan 51
3
Danh mục ký hiệu, chữ viết tắt
T tập mốc thời gian
O tập các đối tượng
D tập dữ liệu giao dịch của các đối tượng
TS tập chuỗi thời gian
Z phép trừ của chuỗi thời gian
SB tập chuỗi ký hiệu
S tập các chuỗi con của chuỗi ký hiệu
A tập chuỗi ký hiệu giao dịch của các đối tượng gian lận
R ngưỡng tương đồng
P tập motif hành vi
F tập thuộc tính
KN N K-nearest neighbor (K láng giềng gần nhất)
SAX Symbolic Aggregate approXimation
DT W Dynamic Time Warping
score Chỉ số chọn mẫu
TP True Positive
FP False Positive
TN True Negative
.
4
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
FN False Negative
P re Precision
Rec Recall
F1 độ đo F1
5
Danh sách hình vẽ
2.1 Sơ đồ tổng quan của mô hình phân tích hành vi trên chuỗi thời
gian. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Mô tả chuỗi thời gian đơn giản: (a) Chuỗi thời gian. (b) Phép trừ
chuỗi của chuỗi thời gian. . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Các hành vi của đối tượng được mô tả dựa trên chuỗi thời gian
đơn giản. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Quy trình khai phá motif. . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Chuyển đổi phép trừ chuỗi của chuỗi thời gian đơn giản thành
chuỗi ký hiệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Tính toán giá trị thuộc tính. . . . . . . . . . . . . . . . . . . . . . . 29
2.7 Minh họa một ma trận nghi ngờ. . . . . . . . . . . . . . . . . . . . 31
3.1 Dữ liệu hoạt động mua hàng. . . . . . . . . . . . . . . . . . . . . . 34
3.2 Chuỗi thời gian thể hiện hành vi thay đổi địa điểm mua hàng của
khách hàng trong 3 năm. . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Chuyển đổi chuỗi thời gian hành vi của từng khách hàng thành
chuỗi ký hiệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Biểu đồ hộp đánh giá kết quả phân lớp từ hành vi thay đổi địa
điểm theo từng thuật toán. . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Biểu đồ hộp đánh giá kết quả phân lớp từ hành vi thay đổi hàng
hóa mua theo từng thuật toán. . . . . . . . . . . . . . . . . . . . . 41
3.6 Biểu đồ hộp đánh giá kết quả phân lớp từ hành vi thay đổi cả địa
điểm và hàng hóa mua theo từng thuật toán. . . . . . . . . . . . . 42
6
Danh sách bảng
2.1 Minh họa ma trận khoảng cách với 5 chuỗi ký hiệu . . . . . . . . . 26
2.2 Ma trận khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Tìm kiếm chuỗi trung tâm motif . . . . . . . . . . . . . . . . . . . 27
3.1 Mô tả dữ liệu hoạt động mua hàng . . . . . . . . . . . . . . . . . . 33
3.2 motif hành vi đáng nghi với R = 0.75 . . . . . . . . . . . . . . . . . 38
3.3 Kết quả phát hiện bất thường dựa trên hành vi thay đổi địa điểm 39
3.4 Kết quả phát hiện bất thường dựa trên hành vi thay đổi hàng hóa
mua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Kết quả phát hiện bất thường dựa trên hành vi thay đổi cả địa
điểm và hàng hóa mua . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Thời gian chạy trung bình của từng thuật toán . . . . . . . . . . . 42
3.7 Kịch bản 4: Kết quả phát hiện bất thường dựa trên việc tổng hợp
điểm đánh giá từ thuật toán Random Forest . . . . . . . . . . . . 43
3.8 Kịch bản 5: Kết quả phát hiện bất thường dựa trên việc tổng hợp
điểm đánh giá từ các thuật toán học máy. . . . . . . . . . . . . . . 43
3.9 Thời gian chạy trung bình của kịch bản 4 và 5 . . . . . . . . . . . 43
7
Danh sách thuật toán
1 Thuật toán khai phá motif trên chuỗi thời gian. . . . . . . . 28
2 Thuật toán phân lớp đối tượng. . . . . . . . . . . . . . . . . . . 30
8
Mở đầu
Lý do chọn đề tài
Phát hiện bất thường là một chủ đề quan trọng và đã được nghiên cứu trong
rất nhiều lĩnh vực [10] tiêu biểu như phát hiện các cuộc tấn công đánh cắp dữ
liệu trong an ninh mạng [27][37] hay cảnh báo lỗi trong các hệ thống giám sát,
cảm biến [36]. Đối với lĩnh vực kinh tế nói chung, bài toán phát hiện bất thường
phổ biến là phát hiện gian lận trong các hoạt động tài chính. Phát hiện gian lận
là một bài toán cấp thiết của nhiều công ty, tổ chức như ngân hàng, bảo hiểm,
các cơ quan nhà nước [28]. Vì vậy, phát hiện gian lận tài chính được rất nhiều
các chuyên gia và nhà nghiên cứu quan tâm và thực hiện hàng loạt công trình
nghiên cứu trong nhiều năm gần đây [4][22][28][32][41].
Cùng với sự phát triển của thời đại công nghệ số hiện nay, các giao dịch tài
chính bùng nổ với một lượng dữ liệu khổng lồ bởi sự phát triển của các hình
thức giao dịch qua mạng và di động. Các hình thức giao dịch này có chi phí thấp
và rất nhanh chóng, tiện lợi. Từ sự phát triển này, việc xử lý giao dịch từ hàng
triệu giao dịch với vô số loại hành vi khác nhau không còn hiệu quả với phương
thức xử lý thủ công. Do đó, yêu cầu đặt ra là cần xây dựng một hệ thống thời
gian thực trích rút được các thông tin thể hiện những hành vi bất thường trong
quá trình hoạt động của đối tượng xấu và sử dụng được các thông tin này để so
khớp, đối chiếu xác định các đối tượng có dấu hiệu nghi vấn gian lận.
Các công trình nghiên cứu liên quan
Dữ liệu chuỗi thời gian được sử dụng rộng rãi để mô tả quá trình hoạt động của
đối tượng và phân tích các bất thường ẩn giấu bên trong [12][19][32][38][44]. Một
cách tiếp cận trong việc phân tích chuỗi thời gian là sử dụng các biểu diễn rời
rạc, với ví dụ tiêu biểu là thuật toán SAX (Symbolic Aggregate approXimation)
và các cải tiến của nó [2][13][33][42][43].
9
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
Khi các chuyên gia phân tích đánh giá rủi ro một đối tượng nào đó, một trong
những cách họ thường sử dụng là xem xét quá trình hoạt động của đối tượng
này trong quá khứ. Họ tổng kết những kinh nghiệm có được từ những đối tượng
gian lận, sử dụng những kinh nghiệm này để đối chiếu với đối tượng đang được
xét và phân tích xem liệu các hành vi của đối tượng này có giống với những hành
vi đáng ngờ hay không. Trong phân tích chuỗi thời gian, các độ đo khoảng cách
được sử dụng để tính toán sự tương đồng giữa các chuỗi mô tả hành vi. Độ đo
DTW (Dynamic Time Warping) thường được sử dụng vì tính linh hoạt trong
việc so khớp chuỗi thời gian [14][17][20][23][25].
Nhiều ứng dụng trí tuệ nhân tạo và khai phá dữ liệu được áp dụng để phát
hiện các yếu tố bất thường ẩn giấu trong dữ liệu [1][11][16][26]. Phân tích xâm
nhập mạng sử dụng KNN [36], AdaBoost [27][37], hồi quy logistic [30] để xác
định các sự kiến bất thường là nguy cơ của các cuộc tấn công mạng. Vorobyev
sử dụng các thuật toán thuộc lớp thuật toán cây quyết định [40] để giảm thiểu
các kết quả phát hiện nhầm trong hệ thống chống gian lận của ngân hàng. Các
gian lận trong giao dịch thẻ tín dụng được đánh giá dựa trên nhiều thuật toán
học máy để đưa ra kết quả tối ưu [5][26].
Mục đích nghiên cứu
Mục tiêu chính của luận văn là trình bày một mô hình áp dụng trong lĩnh vực
phát hiện gian lận giao dịch tài chính. Cụ thể, mô hình đề xuất giải quyết các
vấn đề sau
• Xây dựng thuật toán khai phá motif đưa ra các motif hành vi, thói quen
bất thường mà những đối tượng gian lận sử dụng.
• Phân lớp các đối tượng nhằm xác định nhóm đối tượng có hành vi bất
thường.
• Tận dụng kết quả đánh giá trên từng hành vi để cải thiện kết quả phân lớp
chính xác hơn.
Đối tượng và phạm vi nghiên cứu
Trong khuôn khổ luận văn, tác giả tiếp cận và phân tích những vấn đề của bài
toán phát hiện bất thường trong giao dịch tài chính thông qua sự kết hợp của
phương pháp khai phá motif trong lý thuyết nhận dạng và phát hiện bất thường
10
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
bằng các thuật toán học máy. Có nhiều loại hình giao dịch tài chính như giao dịch
vay nợ, thế chấp, giao dịch tài khoản, giao dịch qua thẻ tín dụng trong đó phổ
biến nhất là giao dịch mua bán hàng hóa trực tiếp. Mô hình đề xuất được áp dụng
cụ thể vào hoạt động mua bán hàng hóa của khách hàng với doanh nghiệp bán lẻ.
Dữ liệu trong giao dịch mua bán hàng hóa bao gồm các thông tin về người
mua; thông tin về hàng hóa như loại hình hàng hóa, giá thành; thông tin giao
dịch như địa điểm giao dịch, tổng chi phí giao dịch, thời gian giao dich. Luận
văn tập trung phân tích hành vi thay đổi địa điểm và loại hàng hóa mua của
khách hàng trong thời gian ba năm từ năm 2015 đến năm 2017.
Cấu trúc luận văn và các đóng góp của tác giả
Nội dung chính của luận văn được trình bày trong ba chương
• Chương 1: Giới thiệu chung về bài toán phát hiện bất thường và các thuật
toán phân lớp trong học máy.
• Chương 2: Trình bày phương pháp xây dựng mô hình nhận dạng motif trong
tập chuỗi thời gian và sử dụng các thuật toán học máy để phân lớp. Qua
đó, xác định được các đối tượng có hành vi bất thường.
• Chương 3: Áp dụng mô hình đưa ra với dữ liệu hoạt động mua hàng.
Trong luận văn này, đóng góp chính của tác giả là xây dựng được sơ đồ tổng
quan của mô hình phân lớp mới dựa trên việc phân tích các thói quen trong giao
dịch của các đối tượng.
11
Chương 1
Giới thiệu chung
1.1 Bài toán phát hiện bất thường
Phát hiện bất thường là bài toán nhận dạng motif trong dữ liệu mà không phù
hợp với hành vi thông thường. Những motif không phù hợp này thường được gọi
là điểm bất thường, điểm ngoại lai, những quan sát trái ngược, ngoại lệ trong
nhiều ngữ cảnh khác nhau [10].
Phát hiệt bất thường được sử dụng rộng rãi trong nhiều lĩnh vực
• Phát hiện gian lận trong hành vi tiêu dùng thẻ tín dụng, bảo hiểm hay chăm
sóc sức khỏe [4][9][22][28][35].
• Phát hiện xâm nhập trong an ninh mạng [27][36][37].
• Phát hiện lỗi trong các hệ thống an toàn và các hoạt động giám sát [14][31].
Một điểm/tập hợp bất thường được định nghĩa là một motif không phù hợp
với hành vi thông thường. Vì vậy, một cách tiếp cận trực tiếp cho bài toán phát
hiện bất thường, là xác định một vùng đại diện cho các hành vi bình thường và
trích rút bất kỳ quan sát nào không thuộc vùng bình thường này là bất thường
[10].
Một bài toán phát hiện bất thường bao gồm bốn khía cạnh chính: nguồn dữ
liệu đầu vào, các loại bất thường, nhãn của dữ liệu và đầu ra của quy trình phát
hiện bất thường [10].
1.1.1 Nguồn dữ liệu đầu vào
Mỗi điểm dữ liệu đầu vào của bài toán được mô tả dưới dạng tập hợp các
thuộc tính. Các thuộc tính này có nhiều kiểu như nhị phân, các giá trị rời rạc
12
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
hay liên tục. Mỗi điểm dữ liệu có thể gồm chỉ một thuộc tính (đơn biến) hay
nhiều thuộc tính (đa biến).
Ngoài ra, các điểm dữ liệu có thể có liên kết với nhau, chẳng hạn dữ liệu dạng
chuỗi [14][38], dữ liệu dạng đồ thị [29]. Trong dữ liệu dạng chuỗi, các điểm dữ
liệu có tính thứ tự tuyến tính, ví dụ như chuỗi thời gian, chuỗi gen, chuỗi protein.
Trong dữ liệu dạng đồ thị, mỗi điểm dữ liệu được biểu diễn dưới dạng đỉnh của
đồ thị và liên kết với nhau bởi các cạnh.
1.1.2 Các loại bất thường
Đặc trưng của bất thường được chia làm ba loại [10]
Bất thường điểm
Nếu một điểm dữ liệu cụ thể được coi là dị thường với phần còn lại của tập dữ
liệu, điểm dữ liệu đó là một bất thường điểm. Loại bất thường này xuất hiện phổ
biến trong các bài toán phát hiện gian lận thẻ tín dụng. Cụ thể, xét một thuộc
tính số tiền tiêu dùng trong dữ liệu giao dịch thẻ tín dụng của các cá nhân, một
giao dịch có số tiền tiêu dùng ở một thời điểm cao đột biến so với hoạt động tiêu
dùng thông thường của cá nhân đó được coi là một bất thường điểm.
Bất thường ngữ cảnh
Một điểm/tập dữ liệu là bất thường trong một ngữ cảnh cụ thể được gọi là
một bất thường ngữ cảnh. Ngữ cảnh trong tập dữ liệu có thể khoảng thời gian
cụ thể, hay các thông tin phân vùng không gian như độ cao, độ sâu. Trong bài
toán phát hiện gian lận thẻ tín dụng, số tiền tiêu dùng trung bình theo tuần cao
đột biến vào những khung thời gian sự kiện giảm giá hoặc dịp lễ hằng năm sẽ
không được coi là bất thường vì hành vi này khớp với xu hướng chi tiêu chung.
Nhưng việc chi tiêu cùng một số tiền đó vào khoảng thời gian thông thường sẽ
được gọi là bất thường ngữ cảnh.
Bất thường nhóm
Nếu một tập hợp các điểm dữ liệu liên quan có sự khác biệt với toàn bộ tập
dữ liệu thì đây là một bất thường nhóm. Một điểm dữ liệu cụ thể trong loại bất
thường này có thể không phải là bất thường điểm, nhưng sự xuất hiện liên tục
các điểm này dẫn đến bất thường trong tập dữ liệu.
13
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
1.1.3 Nhãn dữ liệu
Nhãn của một điểm dữ liệu xác định xem điểm này là bình thường hay bất
thường. Quá trình thu thập dữ liệu được gán nhãn chính xác là phức tạp. Việc
gán nhãn thường được thực hiện một cách thủ công bởi chuyên gia dẫn đến việc
tốn chi phí về mặt thời gian. Thông thường, việc thu thập tập đã gán nhãn từ dữ
liệu bất thường khó khăn hơn việc lấy nhãn từ dữ liệu bình thường. Phụ thuộc
vào số lượng nhãn của tập dữ liệu, bài toàn phát hiện bất thường có thể được
triển khai theo ba hướng [10]
• Phát hiện bất thường có giám sát: Tập dữ liệu luyện được đánh nhãn đầy
đủ với hai loại là bất thường và bình thường. Cách tiếp cận thông thường
là xây dựng mô hình phù hợp từ dữ liệu luyện sau đó dự đoán nhãn cho các
điểm dữ liệu bất kỳ.
• Phát hiện bất thường bán giám sát: Tập dữ liệu luyện chỉ bao gồm các điểm
được gán nhãn bình thường. Cách tiếp cận với trường hợp này là xây dựng
một mô hình tương ứng với hành vi bình thường, và sử dụng mô hình này
để xác định ra các điểm bất thường trong tập dữ liệu [39].
• Phát hiện bất thường không giám sát: Tập dữ liệu không có nhãn. Các kỹ
thuật cho bài toán này dựa trên giả định ngầm các điểm dữ liệu bình thường
có tần suất xuất hiện nhiều hơn các điểm bất thường trong tập dữ liệu [24].
1.1.4 Đầu ra của bài toán
Đầu ra của bài toán phát hiện bất thường gồm hai loại [10]
• Điểm số bất thường: Điểm dữ liệu đại diện cho hành vi của đối tượng được
tính điểm. Sau đó xác định ra số lượng điểm cụ thể có điểm bất thường cao
nhất hoặc đưa ra một ngưỡng điểm số để chọn các điểm bất thường.
• Nhãn: Các đối tượng bất thường và bình thường được phân biệt qua nhãn.
1.2 Bài toán phân lớp và một số thuật toán học máy
1.2.1 Bài toán phân lớp
Phân lớp là quá trình tìm kiếm một mô hình phân biệt các lớp dữ liệu. Mô
hình được xây dựng dựa trên việc phân tích tập dữ liệu luyện và được sử dụng
để dự đoán nhãn lớp của các đối tượng mà chưa biết thông tin nhãn [21].
14
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
Cụ thể, cho tập nhãn lớp C = {1, 2, . . . , C} và tập điểm dữ liệu X ⊂ Rd , ta tìm
một hàm phân lớp f : Rd → C. Với điểm dữ liệu x ∈ X , y = f (x) sẽ gán điểm dữ
liệu vào lớp có nhãn y .
Ngoài ra, f : Rd → RC cũng là một hàm phân lớp với đầu ra là một vector thể
hiện xác suất điểm dữ liệu được gán nhãn vào từng lớp. Điểm dữ liệu sẽ được
gán vào lớp có xác suất gán nhãn cao nhất.
1.2.2 Một số thuật toán học máy
K-láng giềng gần nhất
Thuật toán K -láng giềng gần nhất (KNN) là một trong những thuật toán học
giám sát đơn giản. Thuật toán hoạt động dựa trên nguyên lý nhãn của đối tượng
được xác định dựa trên các đối tượng lân cận nó [15]. Cụ thể, nhãn của điểm
của điểm dữ liệu có thể được xác định qua việc chọn theo đa số (major voting)
nhãn trong K điểm gần nhất hay đánh trọng số cho mỗi điểm gần nhất rồi đưa
ra kết quả.
KNN được ứng dụng trong việc phát hiện chuỗi trạng thái bất thường trong
hoạt động vệ tinh [14]. Nghiên cứu của Ming-Yang Su [36] cũng sử dụng KNN để
phát hiện nhanh chóng các tình huống tấn công mạng dựa trên lưu lượng mạng
bất thường.
Cây quyết định
Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng
để phân lớp các đối tượng dựa vào tập hợp các luật. Thành phần của cây quyết
định bao gồm các nút biểu diễn cho cấu trúc của nhánh. Có hai loại nút, nút
quyết định được sư dụng để ra quyết định và có nhiều nhánh, nút lá là đầu ra
của nút quyết định và không có nhánh con [6].
Cây quyết định được ứng dụng trong việc phát hiện gian lận tín dụng và
thanh toán của ngân hàng [34][40].
Rừng ngẫu nhiên
Rừng ngẫu nhiên (Random Forest) là thuật toán học kết hợp phát triển từ
thuật toán cây quyết định. Ý tưởng thực hiện của thuật toán là luyện hàng loạt
các cây quyết định trên các tập dữ liệu con của tập luyện sinh nhờ phương pháp
15
LUẬN VĂN THẠC SĨ PHẠM NGỌC QUANG ANH
Bagging [7][8].
Cụ thể, ta chọn ra k tập dữ liệu con từ tập dữ liệu luyện. Ứng với mỗi tập
con này, ta chọn một tập thuộc tính con từ không gian thuộc tính và xây dựng
một cây quyết định phân lớp trên bộ dữ liệu này.
Sau khi xây dựng được k cây quyết định, nhãn của điểm dữ liệu dược xác
định dựa trên việc tổng hợp các kết quả đánh nhãn từ các cây quyết định này và
sử dụng phương pháp bỏ phiếu đa số (majority voting) để đưa ra kết luận nhãn
cuối cùng.
AdaBoost
Được đề xuất bởi Yoav Freund và Robert Schapire [18], AdaBoost (Adaptive
Boosting) thuộc loại thuật toán học kết hợp và phân lớp. Ý tưởng của thuật
toán là kết hợp các bộ phân lớp tồi để xây dựng một bộ phân lớp mạnh có tính
chính xác cao hơn [5].
Hồi quy logistic
Hồi quy logistic là thuật toán học máy phổ biến được sử dụng cho học có giám
sát. Thuật toán ước lượng xác suất phân lớp nhị phân dựa trên một hay nhiều
đặc trưng [5]. Hồi quy logistic sử dụng hàm phi tuyến sigmoid để làm hàm phân
lớp. Cụ thể, với một điểm dữ liệu x ∈ Rd và bộ tham số w = {wi }ni=0
1
f (t) = (1.1)
1 + e−t
n
X
t= wi xi
i=0
16
Chương 2
Xây dựng mô hình khai phá motif
cho chuỗi thời gian và phát hiện bất
thường
Nội dung chương 2 đề cập đến quy trình xây dựng mô hình khai phá motif và
phân lớp đối tượng sử dụng các thuật toán học máy.
Phần 2.1 đề xuất mô hình tổng quan quy trình phân tích và phát hiện bất
thường. Phần 2.2 sẽ mô tả quy trình mô hình hóa dữ liệu thành chuỗi thời gian.
Phần 2.3 sẽ đề cập đến khai phá motif bất thường từ những chuỗi thời gian đã
được mô hình hóa. Phần 2.4 mô tả quá trình xây dựng bộ thuộc tính bất thường
và phân lớp. Cuối cùng, phần 2.5 đưa ra các chỉ số đánh giá kết quả phát hiện
bất thường được sử dụng trong luận văn.
2.1 Mô hình tổng quan
Dữ liệu giao dịch trong kinh tế chứa đựng một lượng lớn thông tin thể hiện
hoạt động của các đối tượng. Để xác định được các kịch bản gian lận được che
giấu trong các hoạt động giao dịch này, ta cần xét một chuỗi các giao dịch liên
tiếp do cùng một đối tượng thực hiện [3].
Định nghĩa 2.1. Một chuỗi giao dịch liên tiếp do đối tượng thực hiện được gọi
là một hành vi.
Yêu cầu đặt ra cho một mô hình phát hiện bất thường là tìm ra các motif của
các hành vi do các đối tượng gian lận thực hiện trước giao dịch phát sinh gian
lận. Các motif bất thường sẽ được sử dụng để tìm kiếm những hành vi giao dịch
17