02 - Chap 2 - Các kỹ thuật phân lớp và gom nhóm.pdf

tài liệu môn học máy cho bảo mật

1. https://huit.edu.vn
BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG THƯƠNG THÀNH PHỐ HỒ CHÍ MINH
HỌC MÁY CHO BẢO MẬT
CHƯƠNG 2: CÁC KỸ THUẬT PHÂN LỚP
VÀ GOM NHÓM

2. https://huit.edu.vn
NỘI DUNG
Các kỹ thuật phân lớp dữ liệu
Định nghĩa bài toán phân lớp và gom nhóm
Các kỹ thuật gom nhóm `

3. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Phân lớp (classification)là một bài toán học máy có giám sát
(supervised learning), trong đó mục tiêu:
▪Dự đoán nhãn (label) của một đối tượng dựa trên các đặc trưng
(features) đầu vào, bằng cách học từ các ví dụ đã được gán nhãn
trước.
•Phân lớphọc một hàm ánh xạ từ đầu vào � ∈ ℝ
�
sang một
nhãn rời rạc � ∈ �, sao cho hàm này có thể dự đoán chính xác
nhãn cho các đối tượng chưa thấy.

4. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Phân lớp (classification)
▪Cho một tập huấn luyện:
oTrong đó:
oNhiệm vụ của bài toán phân lớp là tìm một hàm ánh xạ:
Sao cho với đầu vào mới �, mô hình có thể dự đoán đúng nhãn �
y= ℝ
�
→�,
D={�
1,�
1,�
2,�
2,…,�
�,�
�}
�
� ∈ ℝ
�
, là vector đặc trưng của đối tượng thứ ??????
�
� ?????? �: là nhãn tương ứng, thuộc tập rời rạc các nhãn (ví dụ: {“spam”, “not spam”})

5. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Phân lớp (classification):
▪Ví dụ:
oEmail classification: dựa vào tần suất từ khóa (“miễn phí”, “khuyến mãi”),
số liên kết, độ dài email ➔phân loại email là spam hoặc không spam
oImage recognition: phânloạiảnhlà chó, mèo, xe,…
▪Các hệ thống bảo mật sử dụng phân lớp để:
oPhát hiện phần mềm độc hại: Dữ liệu huấn luyện bao gồm các đặc trưng
hành vi thực thi của phần mềm như số lần gọi API, sử dụng bộ nhớ,…➔
phân loại giữa “benign” và “malicious”.

6. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Phân lớp (classification):
▪Các hệ thống bảo mật sử dụng phân lớp để:
oPhát hiện truy cập bất thường (intrusion detection): Phân loại luồng mạng
là "bình thường" hay "xâm nhập" dựa trên đặc trưng như số byte gửi, thời
lượng phiên, cổng sử dụng,...
oPhát hiện cuộc tấn công DDoS dựa trên tần suất yêu cầu.
oPhát hiện gian lận thanh toán (payment fraud detection): Phân loại giao
dịch ngân hàng là “gian lận” hoặc “hợp lệ” ➔Nhận diện giao dịch bất
thường, giảm tổn thất tài chính.

7. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Phân lớp (classification):
▪Ví dụ: Dữ liệu: Số tiền, thời gian, phương thức thanh toán, nhãn
“fraudulent”/“non-fraudulent” (tương ứng 1/0)
➔ kết quả sử dụng logistic regression để phân loại, đạt độ chính xác

8. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Gom nhóm (Clustering):
▪Gom nhóm (clustering) là một bài toán học máy không giám sát
(unsupervised learning), trong đó mục tiêu là chia tập dữ liệu thành
các cụm (clusters) sao cho:
o Các điểm trong cùng cụm thì tương đồng với nhau
oCác điểm ở cụm khác nhau thì khác biệt rõ rệt.

9. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Gom nhóm (Clustering):
▪Cho tập dữ liệu chưa có nhãn:
▪Bài toán gom nhóm tìm một hàm ánh xạ:
nhằm chia tập dữ liệu thành K cụm sao cho các tiêu chí độ tương đồng
trong cụm (intra-cluster similarity) và phân tách giữa các cụm (inter-
cluster separation) được tối ưu.
??????=�
1,�
2,…�
� �ớ?????? �
�∈ℝ
�
�:ℝ
�
→{1,2,3,…�}

10. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Gom nhóm (Clustering):

11. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Gom nhóm (Clustering):
▪ Ví dụ:
oGom nhóm khách hàng theo hành vi mua sắm.
oGom nhóm các văn bản có chủ đề tương tự.
oGom nhóm hình ảnh theo màu sắc chính hoặc bố cục.
▪Các hệ thống bảo mật: Gom nhóm trong bảo mật giúp phân tích
hành vi bất thường, phát hiện mối đe dọa mới mà chưa từng xuất
hiện trong dữ liệu huấn luyện.

12. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Gom nhóm (Clustering):
▪Các hệ thống bảo mật sử dụng gom nhóm:
o Phân tích chiến dịch spam hoặc phishing: Gom nhóm các URL/email có
cấu trúc giống nhau, gợi ý spam cùng nguồn.
oPhát hiện botnet chưa biết trước: Gom nhóm các máy có lưu lượng mạng
tương tự (cùng server điều khiển, cùng kiểu gói tin).
oNhận diện tấn công zero-day: Gom nhóm các mẫu hoạt động hệ thống
khác thường (system calls, tiến trình bất thường) → cụm khác biệt có thể
là dấu hiệu của tấn công mới.

13. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Phân lớp và gom nhóm là hai kỹ thuật cốt lõi trong học máy
ứng dụng vào an ninh mạng
Phân lớp
•Hiệu quả khi đã có
dữ liệu gán nhãn,
dùng để nhận diện
các hành vi đã biết
Gom nhóm
•Hữu ích trong việc
khám phá bất
thường, hỗ trợ
phát hiện sớm các
tấn công chưa biết.
Cả hai kỹ thuật giúp xây
dựng hệ thống bảo mật thông
minh, phản ứng nhanh và
hiệu quả hơn trước các mối
đe dọa ngày càng phức tạp.

14. https://huit.edu.vn
Định nghĩa bài toán phân lớp và gom nhóm
• Câu hỏi thảo luận
▪Vì sao gom nhóm được xem là học không giám sát? Điểm khác
biệt cốt lõi giữa phân lớp và gom nhóm là gì?
▪Có thể kết hợp phân lớp và gom nhóm trong một hệ thống bảo mật
không? Ví dụ.
▪Trong một hệ thống phòng chống tấn công mạng, bạn sẽ ưu tiên
dùng phân lớp hay gom nhóm? Vì sao?

15. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
Classification
Logistic
Regressio
n
Decision
Trees
Decision
Forests
Support
Vector
Machines
(SVM)
Naive
Bayes
k-Nearest
Neighbors
(k-NN)
Neural
Networks

16. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression
▪Logistic Regression (hồi quy logistic) là một trong những thuật toán phổ
biến nhất trong học máy có giám sát
▪Được dùng chủ yếu để phân loại nhị phân (thay vì hồi quy – regression)
▪Ví dụ:dự đoán giao dịch có phải gian lận không, email có phải là spam
không.
▪Hồi quy logistic dự đoán xác suất một mẫu thuộc vào một lớp cụ thể, sử
dụng hàm sigmoid để ánh xạ đầu ra vào khoảng [0,1]. Xác suất này sau
đó được sử dụng để đưa ra quyết định phân lớp.

17. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression: Cách hoạt động
▪ Mô hình tính toán một tổ hợp tuyến tính của các đặc trưng đầu vào
x, với vector trọng số w, và
một hằng số bias w
0
▪Giá trị z sau đó được đưa vào hàm sigmod để tạo ra xác suất
�=[�
1,�
2,…,�
�] �=[�
1,�
2,…,�
�]
�=�
�
�+ �
0= �
0+�
1�
1+�
2�
2+…+�
��
�]
ො�=??????�=
1
1+�
−�

18. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression: Cách hoạt động
▪ Dựa vào xác suất, đưa ra quyết định:
▪Mô hình học các trọng số w bằng cách tối đa hóa khả năng mô hình
tạo ra nhãn đúng (Likelihood Function) hay tối thiểu hóa hàm mất
mát (log loss hay loss-entropy)
ො�=ቊ
1 �ế� ??????(�)≥0.5
0 &#3627408475;ế&#3627408482; ??????&#3627408487;<0.5
Đây là bước phân loại(0
hoặc 1) dựa trên ngưỡng

19. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression: Cách hoạt động
▪ Likelihood function:
▪Hàm loss:
&#3627408447;&#3627408484;=ෑ
&#3627408475;−1
??????
&#3627408486;
&#3627408475;
&#3627408481;
??????
1−&#3627408486;
&#3627408475;
1−&#3627408486;
??????
Với mỗi điểm dữ liệu:
•Nếu nó thuộc lớp 1: xác suất đúng là y
n
•Nếu nó thuộc lớp 0: xác suất đúng là 1-y
n
&#3627408481;
&#3627408475;∈0,1 &#3627408473;à &#3627408475;ℎã&#3627408475; &#3627408481;ℎậ&#3627408481;
Ε=−
1
??????
෍
&#3627408481;=1
??????
ො&#3627408486;
&#3627408481;
log&#3627408486;
&#3627408481;
+(1−ො&#3627408486;
&#3627408481;
)log1−&#3627408486;
&#3627408481;

20. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression: Cách hoạt động
▪ Tối ưu hóa mô hình: Sử dụng gradient descent để cập nhật trọng số
▪ Quyết định phân lớp: sau khi tính y, mô hình phần loại dựa trên
ngưỡng:
oy>=0.5: lớp 1
oy<0.5: lớp 0
&#3627408484;
&#3627408471;←&#3627408484;
&#3627408471;+??????෍
&#3627408481;=1
??????
ො&#3627408486;
&#3627408481;
−&#3627408486;
&#3627408481;
&#3627408485;
&#3627408471;
&#3627408481;

Trong đó, ?????? là learning rate,
&#3627408485;
&#3627408471;
&#3627408481;
là giá trị đặc trưng thứ j của mẫu t.

21. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression:
▪ Ứng dụng:
oPhân loại văn bản: Phân loại email (spam/ham), phân tích cảm xúc (tích
cực/tiêu cực), hoặc phân loại tài liệu.
oY học: Dự đoán xác suất mắc bệnh (ví dụ: ung thư) dựa trên các triệu
chứng hoặc dữ liệu y tế
oY học: Dự đoán xác suất mắc bệnh (ví dụ: ung thư) dựa trên các triệu
chứng hoặc dữ liệu y tế
oTiếp thị: Dự đoán khả năng khách hàng mua sản phẩm dựa trên hành vi
hoặc đặc điểm nhân khẩu học.

22. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression:
▪ Ứng dụng trong lĩnh vực bảo mật:
o Phát hiện Email Spam: Hồi quy logistic phân loại email thành "spam"
hoặc "không spam" dựa trên các đặc trưng như tần suất từ khóa (ví dụ:
"free", "win"), độ dài email, số liên kết, hoặc siêu dữ liệu (metadata) như
thông tin người gửi.
oVí dụ: Một email chứa 5 từ "free", dài 100 từ, và có 3 liên kết được dự
đoán có xác suất 93% là spam

23. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression:
▪ Ứng dụng trong lĩnh vực bảo mật:
o Phát hiện tấn công mạng dạng scan (Scan Detection): Logistic
Regression được sử dụngđể phân biệt traffic bình thường và tấn công dạng
scan (Gates et al. (2006) ). Mô hình được xây dựng từ các đặc trưng: Số
lượng cổng nguồn trung bình trên mỗi IP đích, phần trăm số gói có dữ liệu
(payload), Tỷ lệ SYN/SYN-ACK…
oCách hoạt động: Trích xuất đặc trưng từ log mạng ➔ huấn luyện Logistic
Regression ➔ dự đoán xác suất một luồng là “scan”.

24. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression:
▪ Ưu điểm:
oĐơn giản và hiệu quả: Hồi quy logistic dễ triển khai, yêu cầu tài nguyên
tính toán thấp, phù hợp với các bài toán có dữ liệu tuyến tính hoặc gần
tuyến tính
oDễ triển khai trong hệ thống mạng thời gian thực.
oGiải thích được lý do cảnh báo (đặc trưng nào ảnh hưởng).
oHiệu quả với dữ liệu lớn

25. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression:
▪ Nhược điểm:
oKhông phù hợp với dữ liệu phi tuyến
oKhó mở rộng với mối quan hệ phức tạp

26. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Logistic Regression: Câu hỏi thảo luận
▪ Hàm sigmoid trong Logistic Regression có vai trò gì?
▪Khi nào Logistic Regression có thể không hoạt động tốt?

27. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees
▪ Decision Tree (Cây quyết định) là một mô hình học máy phổ biến
trong các bài toán phân loại và hồi quy
▪Mô hình này sử dụng cấu trúc cây để đưa ra quyết định, trong đó:
oMỗi "nút" của cây đại diện cho một phép kiểm tra hoặc phân chia dữ liệu
oCác "nhánh" đại diện cho kết quả của phép kiểm tra đó
oCác "lá" của cây chứa nhãn phân loại hoặc giá trị dự đoán
▪Cây quyết định giúp đơn giản hóa các bài toán phức tạp bằng cách
chia nhỏ chúng thành các quyết định dễ dàng thực hiện.

28. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees
Source: analyticsvidhya.com

29. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees
▪Phân loại theo biến mục tiêu:
o Classification Trees: Được sử dụng để dự đoán kết quả dạng phân loại
(categorical outcomes), ví dụ: email là spam hay không spam. Cây thực
hiện phân chia dữ liệu dựa trên các đặc trưng (features) nhằm gán nhãn cho
dữ liệu vào các nhóm đã được xác định trước.
o Regression Trees: Được sử dụng để dự đoán giá trị liên tục, chẳng hạn
như giá nhà. Thay vì gán nhãn phân loại, cây đưa ra dự đoán số (numerical
prediction) dựa trên các đặc trưng đầu vào.
Source:ibm.com

30. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees
▪Phân loại theo thuật toán:
o ID3 (Iterative Dichotomiser 3): Thuật toán này sử dụng entropy và
information gain để đánh giá các điểm phân chia dữ liệu
oC4.5: Là phiên bản nâng cấp của ID3, sử dụng information gain hoặc gain
ratio để xác định điểm chia trong cây quyết định
oCART (Classification and Regression Trees): sử dụng Gini impurity để xác
định thuộc tính phân chia tốt nhất. Gini impurity đo lường xác suất sai khi
gán nhãn ngẫu nhiên, giá trị càng thấp thì phân chia càng tốt.
Source:ibm.com

31. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Công thức
▪ Cây quyết định thường sử dụng các tiêu chí như entropy hoặc Gini
index để xác định cách phân chia dữ liệu tại mỗi nút.
▪Entropy là một hàm đo lường mức độ ngẫu nhiên của một biến
ngẫu nhiên, được tính dựa trên xác suất của các lớp trong tập dữ
liệu.
▪Entropy cao biểu thị dữ liệu có sự phân bố đồng đều giữa các lớp,
trong khi entropy thấp cho thấy một lớp chiếm ưu thế.
Source:ibm.com

32. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Công thức
▪ Entropy
▪Ví dụ: cho tập dữ liệu có 4, 2 mẫu thuộc lớp A, 2 mẫu thuộc lớp B.
Tính entropy của tập dữ liệu:
oXác suất của lớp A, ??????
&#3627408436;=
2
4
=0.5
oXác suất của lớp B, ??????
&#3627408437;=
2
4
=0.5
Source:ibm.com
&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408439;=−෍
&#3627408470;=1
&#3627408472;
&#3627408477;
&#3627408470;log
2&#3627408477;
&#3627408470;
Trong đó:
▪p
ilà xác suất của lớp thứ i trong tập dữ
liệu D
▪k là số lượng lớp trong tập dữ liệu
▪Log
2là logarit cơ số 2, dùng để đo
lường số bit thông tin
&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408439;=−(0.5log
20.5+0.5log
20.5)
&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408439;=−0.5∗−1+0.5∗−1=1

33. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Công thức
▪ Entropy:
oEntropy luôn ≥ 0
oĐơn vị của entropy là bit (vì log cơ số 2)
oTrong cây quyết định, entropy được dùng để tính Information Gain nhằm
chọn thuộc tính chia tốt nhất

34. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Công thức
▪ Giảm entropy (Information Gain): còn gọi là độ lợi thông tin, là sự
khác biệt giữa entropy của tập dữ liệu tại nút cha (parent node) và
entropy trung bình có trọng số của các tập con sau khi phân chia
dựa trên một đặc trưng
▪Đặc trưng với Information Gain cao nhất được chọn để phân chia,
vì nó giảm sự không chắc chắn nhiều nhất.
▪Information Gain được tính dựa trên entropy

35. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Công thức
▪ Giảm entropy (Information Gain):
▪Trong đó:
oS: tập dữ liệu của nút cha,
oA: đặc trưng được chọn để phân chia
oValues(A): tập con của S chứa các mẫu có giá trị v cho đặc trung A
oS
v: Tập con của S chứa các mẫu có giá trị v cho đặc trưng A
o
&#3627408454;??????
&#3627408454;
Tỷ lệ kích thước của tập con S
v so với tập dữ liệu gốc S
&#3627408444;&#3627408475;&#3627408467;&#3627408476;&#3627408479;&#3627408474;&#3627408462;&#3627408481;??????&#3627408476;&#3627408475; &#3627408442;&#3627408462;??????&#3627408475;&#3627408454;,&#3627408436;=&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408480;− ෍
&#3627408483; ∈????????????&#3627408473;&#3627408482;&#3627408466;&#3627408480;&#3627408436;
&#3627408454;
&#3627408483;
&#3627408454;
&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;(&#3627408454;
&#3627408483;)

36. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Giảm entropy (Information Gain): giả sử tập dữ liệu S có 100
email, 50 spam (p
1=0.5), và 50 không spam (p
2=50)
oEntropy ban đầu: &#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408454;=−0.5log
20.5+0.5log
20.5=1
oChọn đặc trưng phân chia: có chứa từ “free”:
•Tập con 1 (S
1 có từ “free”): 40 email, 35 spam, 5 spam
Source:ibm.com
&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408454;
1=−
35
40
log
2(
35
40
)+
5
40
log
2
5
40
≈0.544

37. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Giảm entropy (Information Gain):
oChọn đặc trưng phân chia: có chứa từ “free”:
•Tập con 2 (S
2 không có từ “free”): 60 email, 15 spam, 45 không spam
•Tính Information Gain:
oĐặc trưng này có Information Gain là 0.295, và nếu nó cao hơn so với các đặc
trưng khác, nó sẽ được chọn để phân chia.
Source:ibm.com
&#3627408440;&#3627408475;&#3627408481;&#3627408479;&#3627408476;&#3627408477;&#3627408486;&#3627408454;
2=−
15
60
log
2(
15
60
+
45
60
log
2
45
60
≈0.811
&#3627408444;&#3627408475;&#3627408467;&#3627408476;&#3627408479;&#3627408474;&#3627408462;&#3627408481;??????&#3627408476;&#3627408475; &#3627408442;&#3627408462;??????&#3627408475;=1−
40
100
0.544+
60
100
0.811≈1−0.218+0.487=0.295

38. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Gini Impurity (Độ không thuần khiết Gini): chỉ số dùng để đo
lường độ phân tán của các lớp trong một tập dữ liệu.
▪Được sử dụng trong các thuật toán cây quyết định (Decision Tree)
để đánh giá chất lượng của việcphân chia dữ liệu tại mỗi nút trong
quá trình xây dựng cây quyết định.

39. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Gini Impurity (Độ không thuần khiết Gini):
▪Trong đó:
op
i là xác suất của lớp thứ I trong tập dữ liệu D
ok là số lượng lớp trong tập dữ liệu
&#3627408442;??????&#3627408475;??????&#3627408439;=1−෍
&#3627408470;=1
&#3627408472;
&#3627408477;
&#3627408470;
2

40. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Gini Impurity (Độ không thuần khiết Gini): ví dụ có một tập dữ
liệu với 4 mẫu, trong đó 2 mẫu thuộc lớp A, 2 mẫu thuộc lớp B
oXác suất của mỗi lớp
oTính Gini Impurity:
oVậy Gini Impurity của tập dữ liệu này là 0.5, nghĩa là có sự phân chia đều
giữa hai lớp A và B.
??????
&#3627408436;=
2
4
=0.5
??????
&#3627408437;=
2
4
=0.5
&#3627408442;??????&#3627408475;??????&#3627408439;=1−&#3627408477;
&#3627408436;
2
+&#3627408477;
&#3627408436;
2
&#3627408442;??????&#3627408475;??????&#3627408439;=1−0.5
2
+0.5
2
=1 - 0.5=0.5

41. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Khởi tạo: Mô hình bắt đầu với toàn bộ tập dữ liệu tại "nút gốc" của cây.
▪Chọn đặc trưng để phân chia:
oTại mỗi nút, thuật toán quyết định phân chia dữ liệu thành các nhóm con dựa trên
một thuộc tính hoặc tính năng. Quá trình phân chia tiếp tục cho đến khi đạt được
một tiêu chí dừng, chẳng hạn như độ sâu cây tối đa hoặc không còn phân chia hữu
ích nữa.
oQuyết định phân chia tại mỗi nút được thực hiện dựa trên các tiêu chí như
Information Gain (Tăng thông tin) hoặc Gini Impurity (Độ tinh khiết Gini).

42. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cách hoạt động của Decision Tree
▪ Lặp lại: Quá trình phân chia tiếp tục tại mỗi nút con cho đến khi
một trong các điều kiện dừng được thỏa mãn:
oTất cả các mẫu trong nút thuộc cùng một lớp (hoặc giá trị gần giống trong
hồi quy).
oĐạt đến độ sâu tối đa của cây (max_depth).
oSố lượng mẫu trong nút nhỏ hơn ngưỡng tối thiểu (min_samples_leaf).
▪Dự đoán: Mỗi nút lá được gán nhãn dựa trên lớp chiếm đa số (phân
loại) hoặc giá trị trung bình (hồi quy) của các mẫu trong nút đó..

43. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Ưu điểm
▪ Dễ hiểu và giải thích: Cây quyết định cung cấp một biểu diễn trực quan
dễ hiểu, cho phép người dùng hiểu được logic phân loại
▪Không yêu cầu nhiều tiền xử lý dữ liệu: Decision Tree có thể xử lý các
dữ liệu dạng phi cấu trúc và không yêu cầu các bước chuẩn hóa hay biến
đổi đặc trưng.
▪Xử lý được cả dữ liệu số và phân loại: Có thể hoạt động với các đặc
trưng liên tục và rời rạc mà không cần mã hóa phức tạp, thể áp dụng cho
cả bài toán phân loại (classification) và hồi quy (regression)

44. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: nhược điểm
▪ Dễ bị overfitting: Decision Tree dễ bị overfitting, đặc biệt là khi cây quá
sâu và phân chia dữ liệu quá chi tiết.
▪Nhạy cảm với dữ liệu không cân bằng: Hiệu suất có thể giảm khi các lớp
không cân bằng.
▪Ít chính xác hơn so với các mô hình khác: Cây quyết định thường kém
chính xác hơn so với các mô hình như SVM hoặc Decision Forests
▪Có thể tạo ra các cây quá phức tạp: Nếu không được kiểm soát chặt chẽ,
Decision Tree có thể trở nên quá phức tạp và khó giải thích.

45. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: ứng dụng
▪ Phân loại khách hàng trong marketing: phân loại khách hàng theo
hành vi mua sắm hoặc nhu cầu sử dụng sản phẩm, giúp tối ưu hóa
chiến lược marketing.
▪Phân loại bệnh nhân theo loại bệnh (như ung thư hay không) dựa
trên các đặc điểm y tế như kết quả xét nghiệm, tiền sử bệnh, v.v.
Source:ibm.com

46. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: ứng dụng
▪ Phát hiện xâm nhập: phân tích các dữ liệu mạng và xác định các
hành vi bất thường có thể là dấu hiệu của một cuộc tấn công.
oVí dụ, việc phân tích lưu lượng mạng có thể giúp phát hiện các cuộc tấn
công DDoS (tấn công từ chối dịch vụ phân tán) hoặc hành vi xâm nhập bất
hợp pháp.
▪Phát hiện phần mềm độc hại (malware): phân loại các filetải về
hoặc hoạt động trên hệ thống thành các loại ➔xác định các phần
mềm độc hại tiềm ẩn dựa trên các đặc điểm nhất định.
Source:ibm.com

47. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Câu hỏi thảo luận
▪So sánh ưu điểm và nhược điểm của Decision Tree với Logistic
Regression. Khi nào sử dụng Decision Tree?
▪Trường hợp nào sử dụng Logistics Regression?
Source:ibm.com

48. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Trees: Cho dữ liệu mẫu sau
▪Xác định thuộc tính phân chia đầu tiên bằng Information Gain.
▪Vẽ cây quyết định tương ứng với dữ liệu trên
Source:ibm.comSTT Thời tiếtNhiệt độ Độ ẩm Gió
Chơi
pickleball
1 Nắng Nóng Cao Yếu Không
2 Nắng Nóng Cao Mạnh Không
3 Âm u Nóng Cao Yếu Có
4 Mưa Mát Cao Yếu Có
5 Mưa Lạnh Bình thườngYếu Có

49. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪ Là một phương pháp học máy thuộc nhóm ensemble learning (học tổ
hợp), được thiết kế để khắc phục nhược điểm của cây quyết định đơn lẻ,
kết hợp nhiều cây quyết định (decision trees) để tạo ra một mô hình
mạnh mẽ hơn, cải thiện độ chính xác và khả năng tổng quát hóa.
▪Mỗi cây quyết định được huấn luyện trên một tập hợp con ngẫu nhiên
của dữ liệu và các đặc trưng sử dụng kỹ thuật bagging, giúp tăng cường
tính tổng quát hóa và giảm thiểu hiện tượng overfitting
▪ Kết quả cuối cùng được tổng hợp từ các cây, thường thông qua bỏ phiếu
đa số (cho phân loại) hoặc trung bình (cho hồi quy).
Source:ibm.com

50. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
Source:ibm.com

51. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests): Hai thành phần tạo ra sự
độc lập giữa các cây
Source:ibm.com
Decision
Forest
Bagging
(Bootstrap
Aggregation)
Random
Feature
Selection

52. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests): Hai thành phần tạo ra sự độc
lập giữa các cây
▪ Bagging (Bootstrap Aggregation): là một kỹ thuật giúp giải quyết vấn
đề high variance (độ biến thiên cao) của cây quyết định đơn lẻ giúp mô
hình tổng quát hóa tốt hơn (generalization) và ổn định hơn.
oTạo ra nhiều biến thể của tập huấn luyện bằng cách lấy mẫu ngẫu nhiên có hoàn
lại từ tập dữ liệu gốc.
oMỗi mẫu được dùng để huấn luyện một cây.
oCác mẫu có thể chứa phần tử lặp lại (do lấy mẫu có hoàn lại).
Source:ibm.com

53. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests): Hai thành phần tạo ra sự
độc lập giữa các cây
▪ Bagging (Bootstrap Aggregation): các bước thực hiện
oTạo dữ liệu huấn luyện bằng lấy mẫu Bootstrap: Từ tập dữ liệu gốc X, thực
hiện lấy mẫu ngẫu nhiên có hoàn lại để tạo ra B tập huấn luyện con:
X
1,X
2,...,X
B
oMỗi tập &#3627408459;
??????có kích thước bằng tập gốc, nhưng có thể có mẫu lặp lại và một
số mẫu trong &#3627408459;có thể không xuất hiện trong &#3627408459;
??????.
Source:ibm.com

54. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests): Hai thành phần tạo ra sự
độc lập giữa các cây
▪ Bagging (Bootstrap Aggregation): các bước thực hiện
oVí dụ: có tập dữ liệu gốc
o Thực hiện bootstrap sampling 3 lần (với ??????=3):
Source:ibm.com
D = [1, 2, 3, 4, 5, 6]
D1​=[2,2,4,6,6,1]
D2​=[3,4,5,5,1,2]
D3​=[1,1,1,3,5,6]
Có lặp lại các giá trị, nhưng vẫn giữ nguyên kích thước.

55. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests) dựa trên hai kỹ thuật chính:
bagging và random feature selection
▪ Random Feature Selection (Lựa chọn đặc trưng ngẫu nhiên): Là thành
phần cốt lõi thứ hai trong thuật toán Random Forest, giúp tăng tính độc
lập giữa các cây và giảm sự tương quan giữa chúng.
oTại mỗi nút chia, thay vì xét tất cả đặc trưng, thuật toán chỉ xét một tập con ngẫu
nhiên các đặc trưng
oTrong số các đặc trưng được chọn ngẫu nhiên này, thuật toán vẫn chọn đặc trưng
tốt nhất để phân chia ➔ các cây phải khám phá không gian đặc trưng theo cách
khác nhau ➔tăng đa dạng giữa các cây.

56. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests) dựa trên hai kỹ thuật
chính: bagging và random feature selection
▪ Random Feature Selection (Lựa chọn đặc trưng ngẫu nhiên):

57. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests): Hai thành phần tạo ra sự
độc lập giữa các cây
▪ Các bước thực hiện
oHuấn luyện mô hình con: Với mỗi tập dữ liệu bootstrap X
i​, huấn luyện một
cây quyết định T
i.
oKết hợp dự đoán từ các cây: Mỗi cây đưa ra dự đoán riêng tùy theo bài
toán
Source:ibm.com

58. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests): Hai thành phần tạo ra sự độc
lập giữa các cây
▪ Các bước thực hiện
o Nếu là bài toán hồi quy
oNếu bài toán là phân loại: dự đoán cuối cùng thường là lớp nhận được số phiếu
đa số
&#3627408436;&#3627408467;(&#3627408485;)=&#3627408474;&#3627408476;&#3627408465;&#3627408466;(&#3627408467;
1&#3627408485;,&#3627408467;
2&#3627408485;…&#3627408467;
&#3627408455;&#3627408485;) trong đó f
t(x) là lớp mà cây thứ t dự đoán.
T: số cây&#3627408467;(&#3627408485;)=
1
&#3627408455;
෍
&#3627408481;=1
&#3627408455;
&#3627408467;
&#3627408481;(&#3627408485;)

59. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪Ứng dụng của Decision Forests:
oPhân loại (Classification): Sử dụng để phân loại dữ liệu vào các nhóm đã
định sẵn (ví dụ: phân loại email là spam hay không).
oHồi quy (Regression): Dự đoán giá trị liên tục, như dự đoán giá bất động
sản.
oPhát hiện bất thường (Anomaly Detection): Random Forests có thể phát
hiện các bất thường trong dữ liệu có nhiều chiều, chẳng hạn như trong bảo
mật mạng
Source:ibm.com

60. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪Ứng dụng của Decision Forests:
oPhát hiện xâm nhập (Intrusion Detection): Phát hiện các mẫu bất thường
trong lưu lượng mạng có thể chỉ ra hoạt động độc hại. Random Forests có
thể xử lý dữ liệu có nhiều chiều và nhận diện các mẫu phức tạp
oPhát hiện hành vi bất thường (Anomaly Detection): Bằng cách đo lường độ
gần gũi giữa các điểm dữ liệu, Decision Forests có thể nhận diện các hành
vi bất thường trong mạng hoặc hệ thống
Source:ibm.com

61. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪Ưu điểm:
oĐộ chính xác cao: Random Forests thường cho độ chính xác cao ngay cả
khi không cần tối ưu hóa nhiều tham số
oKhả năng xử lý song song: Vì mỗi cây được huấn luyện độc lập, Random
Forests có thể được xử lý song song, giúp tiết kiệm thời gian tính toán với
các bộ dữ liệu lớn
oKhả năng chống overfitting tốt: Nhờ việc trung bình hóa kết quả từ nhiều
cây, Random Forests giảm thiểu hiện tượng overfitting so với các cây
quyết định đơn lẻ
Source:ibm.com

62. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪Nhược điểm:
oPhức tạp: Mặc dù Random Forests rất mạnh mẽ, nhưng chúng khó giải
thích hơn so với các cây quyết định đơn lẻ. Điều này có thể là một hạn chế
trong các ứng dụng yêu cầu giải thích mô hình
oThời gian huấn luyện lâu: Dù có thể xử lý song song, nhưng Random
Forests vẫn có thể mất nhiều thời gian huấn luyện, đặc biệt khi dữ liệu rất
lớn
oTốn bộ nhớ: Random Forests yêu cầu nhiều bộ nhớ hơn so với các mô hình
đơn giản như hồi quy tuyến tính
Source:ibm.com

63. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪Câu hỏi thảo luận
oRandom Forest và Decision Tree khác nhau ở điểm nào? Khi nào nên dùng
Random Forest thay cho Decision Tree?
Source:ibm.com

64. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Decision Forests (Random Forests)
▪Cho dữ tập dữ liệu
▪Xây dựng cây Decision Forests dựa trên tập dữ liệu trên Contains
Free
NumLinks Length
Class
(Spam/Not Spam)
1Small Short Spam
0Small Short Not Spam
1Large Long Spam
0Large Long Not Spam
1Small Long Spam
0Small Long Not Spam

65. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Support Vector Machines (SVM) là một thuật toán học máy có
giám sát (supervised learning), được sử dụng chủ yếu cho các bài
toán phân loại (classification) và hồi quy (regression).
▪SVM tìm kiếm một siêu phẳng (hyperplane) trong không gian đa
chiều để phân tách các lớp dữ liệu một cách tối ưu, sao cho khoảng
cách từ siêu phẳng đến các điểm dữ liệu gần nhất của các lớp (gọi
là vector hỗ trợ -support vectors) là lớn nhất.
Source:ibm.com

66. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
Giả sử có hai nhóm điểm trên một mặt phẳng.
SVM sẽ tìm một đường thẳng (trong trường
hợp 2D) hoặc một mặt phẳng (trong trường
hợp 3D) hoặc một siêu phẳng (trong trường
hợp nhiều chiều hơn) sao cho nó chia đôi hai
nhóm này một cách rõ ràng nhất, và khoảng
cách từ đường/mặt/siêu phẳng này đến các
điểm gần nhất của mỗi nhóm là lớn nhất có
thể.

67. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs
Source:ibm.com
Phân loại
Theo loại bài
toán
Classification
SVM
Support Vector
Regression
Theo khả năng
phân tách dữ
liệu
Linear SVM
Non-linear SVM
Theo số lớp
Binary SVM
Multi-class SVM
Theo loại dữ liệu
huấn luyện
Hard-margin
SVM
Soft-margin
SVM
One-class SVM

68. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs - Theo loại dữ liệu huấn luyện
oHard-margin SVM: Yêu cầu dữ liệu hoàn toàn phân tách được mà không
có lỗi.
o Soft-margin SVM: Cho phép một số lỗi phân loại để xử lý dữ liệu thực tế,
sử dụng tham số C để cân bằng giữa lề lớn và lỗi phân loại.
oOne-class SVM: Dùng cho phát hiện bất thường (anomaly detection), chỉ
cần dữ liệu từ một lớp để huấn luyện.
Source:ibm.com

69. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs - Theo số lớp
oBinary SVM: Phân loại hai lớp (ví dụ: tích cực/tiêu cực).
o Multi-class SVM: Phân loại nhiều hơn hai lớp, thường sử dụng các chiến
lược như One-vs-Rest hoặc One-vs-One.
Source:ibm.com

70. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs - Theo loại bài toán
oClassification SVM: Dùng để phân loại dữ liệu thành các lớp riêng biệt (ví
dụ: phân loại email là spam hoặc không spam).
o Support Vector Regression: Dùng để dự đoán giá trị liên tục (ví dụ: dự
đoán giá cổ phiếu).
Source:ibm.com

71. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs - Theo khả năng phân tách dữ liệu
oLinear SVM: là phiên bản đơn giản nhất của SVM, chỉ dùng được khi dữ
liệu tuyến tính hoàn hảo
oLinear SVM sử dụng một đường thẳng (trong 2D) hoặc một siêu phẳng
(hyperplane) trong không gian nhiều chiều để phân chia dữ liệu thuộc các
lớp khác nhau.
Source:ibm.com

72. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs
oNon-linear SVM: Khi dữ liệu không thể phân chia bằng một đường thẳng
➔dùng SVM phi tuyến (Non-Linear SVM)
oTrong đa số bài toán thực tế, dữ liệu không phân chia tuyến tính hoàn hảo
➔ Non-Linear SVM kết hợp với kernel là lựa chọn phổ biến nhất.
oMột số kernel thường dùng: RBF (Gaussian), Polynomial, Sigmoid.
Source:ibm.com

73. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Phân loại SVMs

74. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSiêu phẳng (Hyperplane): hyperplane đóng vai trò như một ranh giới quyết
định (decision boundary) giúp phân loại tập dữ liệu. Đây là mặt phẳng
phân tách các điểm dữ liệu thuộc các lớp khác nhau.
oHyperplane là một không gian con tuyến tính (affine subspace) có số chiều
là p - 1, khi dữ liệu nằm trong không gian p chiều.
Source:ibm.com

75. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSiêu phẳng (Hyperplane):
Không gian dữ liệu Hyperplane
2 chiều (2D) Một đường thẳng
3 chiều (3D) Một mặt phẳng phẳng
n chiều Một không gian con (n−1)
oMột hyperplane “tốt” sẽ giúp phân loại
mạnh mẽ hơn và tổng quát hóa tốt hơn.

76. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSiêu phẳng (Hyperplane): Công thức tổng quát của hyperplane
oTrong đó:
Source:ibm.com
&#3627408484;
&#3627408455;
&#3627408485;+&#3627408463;=&#3627408484;
1&#3627408485;
1+ &#3627408484;
2&#3627408485;
2+⋯+&#3627408484;
&#3627408475;&#3627408485;
&#3627408475;+&#3627408463;=0
&#3627408484;=&#3627408484;
1,&#3627408484;
2,…&#3627408484;
&#3627408475;: vector trọng số
Ԧ&#3627408485;=&#3627408485;
1,&#3627408485;
2,…&#3627408485;
&#3627408475;: vector đặc trưng của dữ liệu
b: hệ số điều chỉnh (bias)

77. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSiêu phẳng (Hyperplane): Các điểm dữ liệu được phân loại như sau:
oMục tiêu SVM: tìm hyperplane tối ưu sao cho:
•Phân loại đúng các điểm dữ liệu huấn luyện
•Tối đa hóa margin — khoảng cách đến các điểm gần nhất (support vectors)
Source:ibm.com
??????ế&#3627408482;&#3627408485;.&#3627408484;+&#3627408463;≥0:&#3627408455;ℎ&#3627408482;ộ&#3627408464; &#3627408473;ớ&#3627408477;+1
??????ế&#3627408482;&#3627408485;.&#3627408484;+&#3627408463;≤0:&#3627408455;ℎ&#3627408482;ộ&#3627408464; &#3627408473;ớ&#3627408477;−1
??????ế&#3627408482;&#3627408485;.&#3627408484;+&#3627408463;=0:??????ằ&#3627408474; &#3627408481;&#3627408479;ê&#3627408475; đườ&#3627408475;&#3627408468; &#3627408443;&#3627408486;&#3627408477;&#3627408466;&#3627408479;&#3627408477;&#3627408473;&#3627408462;&#3627408475;&#3627408466;

78. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM:
oSupport Vectors: Support vectors là những
điểm dữ liệu gần nhất với hyperplane, đóng
vai trò then chốt trong việc xác định vị trí
của hyperplane (siêu phẳng) –ranh giới
phân chia các lớp dữ liệu trong không gian
đặc trưng.
oCác điểm support vector ảnh hưởng trực
tiếp đến việc xác định hyperplane.

79. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: margin (Biên)
oLà khoảng cách vuông góc từ siêu phẳng đến các support vectors.
oSVM tìm hyperplane sao cho margin là lớn nhất → giúp mô hình tổng quát
tốt hơn (khả năng phân loại chính xác trên dữ liệu chưa thấy).
oKhi margin càng lớn, mô hình tổng quát hóa càng tốt → ít bị ảnh hưởng
bởi nhiễu, giảm nguy cơ overfitting.
oKhi margin nhỏ, mô hình dễ nhạy cảm với biến động nhỏ trong dữ liệu →
dễ bị overfit.
Source:ibm.com

80. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: margin (Biên)
oCông thức tính margin:
&#3627408474;&#3627408462;&#3627408479;&#3627408468;??????&#3627408475;=
2
&#3627408484;
oMargin sẽ đạt giá trị lớn nhất
khi w có độ dài nhỏ nhất.

81. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM:
oHard Margin SVM: Trong trường hợp dữ liệu có thể phân tách tuyến tính
hoàn hảo, tất cả các support vectors sẽ nằm chính xác trên biên của margin
(với điều kiện &#3627408486;
&#3627408470;&#3627408484;
&#3627408455;
&#3627408485;
&#3627408470;+&#3627408463;=1đối với mỗi support vector).
oSoft Margin SVM: Khi dữ liệu không thể phân
tách hoàn hảo, slack variables được sử dụng để
cho phép một số điểm nằm sai phía của margin,
giúp mô hình không bị overfitting.

82. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSlack Variables: là những giá trị cho phép các điểm dữ liệu lệch khỏi
margin hoặc bị phân loại sai trong trường hợp soft margin ➔ cho phép
một số điểm vi phạm margin mà không ảnh hưởng quá nhiều đến kết quả
phân loại của mô hình.
oHàm mục tiêu được tối thiểu hóa trong Soft Margin SVM:
&#3627408474;??????&#3627408475;??????&#3627408474;??????&#3627408487;&#3627408466;
1
2
&#3627408484;
2
+&#3627408438;෍
&#3627408470;=1
&#3627408475;
??????
&#3627408470;Với các ràng buộc: &#3627408486;
&#3627408470;&#3627408484;
&#3627408455;
&#3627408485;
&#3627408470;+&#3627408463;>1,??????
&#3627408470;≥0,∀??????=1,2..&#3627408475;
C: Tham số hiệu chỉnh, kiểm soát mức độ phạt các lỗi phân loại.

83. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSlack Variables:&#3627408438;෍
&#3627408470;=1
&#3627408475;
??????
&#3627408470;
??????
&#3627408470; đ&#3627408476;&#3627408473;ườ&#3627408475;&#3627408468;&#3627408474;ứ&#3627408464;độ&#3627408483;??????&#3627408477;ℎạ&#3627408474;&#3627408464;ủ&#3627408462;đ??????ể&#3627408474;&#3627408465;ữ&#3627408473;??????ệ&#3627408482;&#3627408481;ℎứ??????
C: là tham số hiệu chỉnh, quyết định mức độ phạt các lỗi ??????
&#3627408470;. C lớn sẽ phạt nặng các lỗi, dẫn đến ít vi
phạm hơn nhưng biên có thể hẹp hơn.
Thành phần này liên quan đến tổng lỗi phân loại hoặc vi phạm
biên. Tối ưu hóa giá trị này tương đương với việc giảm số lượng
và mức độ của các điểm dữ liệu vi phạm biên hoặc bị phân loại
sai.
??????
&#3627408470;=0, Điểm dữ liệu nằm đúng trên hoặc ngoài biên (đáp ứng điều kiện phân tách tối ưu)
??????
&#3627408470;>0, Điểm dữ liệu bị phân loại sai (nằm ở phía sai của siêu phẳng)
0<??????
&#3627408470;≤1, Điểm dữ liệu nằm trong biên nhưng ở đúng phía của siêu phẳng

84. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM
oSlack Variables:

85. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oKernel là kỹ thuật chính giúp SVM xử lý dữ liệu phi tuyến tính.
oKhi dữ liệu không thể phân tách bằng đường thẳng (linear) ➔ cần ánh xạ
dữ liệu từ không gian gốc sang một không gian đặc trưng có chiều cao
hơn, nơi mà các lớp có thể phân chia tuyến tính.
oKernel Trick cho phép thực hiện điều đó mà không cần tính toán trực tiếp
ánh xạ, chỉ cần tính toán tích vô hướng (dot product) giữa các điểm trong
không gian cao đó.
Source:ibm.com

86. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions

87. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oLinear Kernel: phù hợp khi dữ liệu tuyến tính khi các lớp dữ liệu có thể
được phân chia rõ ràng bằng một đường thẳng (trong không gian 2D), hoặc
siêu phẳng (trong không gian nhiều chiều).
oHàm kernel tuyến tính cơ bản: là tích vô hướng giữa hai vector &#3627408485;và &#3627408486;
trong không gian gốc.
oLinear Kernel: Linear kernel thường được dùng trong bài toán phân loại
văn bản: Phát hiện email spam, phân tích cảm xúc văn bản
Source:ibm.com
&#3627408446;&#3627408485;,&#3627408486;=&#3627408485;
&#3627408455;
&#3627408486;=෍
&#3627408470;=1
&#3627408475;
&#3627408485;
&#3627408470;&#3627408486;
&#3627408470;

88. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oLinear Kernel:

89. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oPolynomial Kernel: giúp SVM có khả năng mô hình hóa các mối quan hệ
phức tạp hơn giữa các điểm dữ liệu (dữ liệu không thể phân tách bằng một
đường thẳng)
oThay vì chỉ xem xét mối liên hệ tuyến tính (x.y) như Linear kernel,
Polynomial kernel thêm các thành phần đa thức (bậc cao hơn), ví dụ như
&#3627408485;
2
y,&#3627408485;
3
y,x
3
.. ➔ có thể bắt được các ranh giới phi tuyến giữa các lớp dữ liệu.
Source:ibm.com

90. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oPolynomial Kernel:
oTrong đó:
Source:ibm.com
&#3627408446;&#3627408485;,&#3627408486;=&#3627408485;
&#3627408455;
&#3627408486;+&#3627408464;
&#3627408465;

&#3627408485;
&#3627408455;
&#3627408486;: tích vô hướng giữa hai vector đặc trưng
c: một hằng số (thường ≥ 0), giúp kiểm soát mức độ tương tác giữa các chiều.
d: bậc của đa thức, điều chỉnh độ phi tuyến:
▪ d=1: tương đương linear kernel.
▪??????=2: xét thêm các tương tác bậc hai như &#3627408485;
1&#3627408485;
2
▪??????>2: cho phép ranh giới rất phi tuyến.

91. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oPolynomial Kernel: Polynomial kernel
thường được dùng trong các bài toán nhận
dạng hình ảnh (image recognition) hoặc
những nơi mà mối quan hệ giữa các đặc
trưng là phi tuyến, phát hiện được các mô
hình bậc cao
oVí dụ như hình dạng, cấu trúc hình học
trong ảnh.

92. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oCông thức
&#3627408446;(&#3627408485;,&#3627408486;)=tanh??????&#3627408485;
&#3627408455;
&#3627408486;+&#3627408464;
α (alpha) là một hệ số điều chỉnh độ dốc (slope) của hàm sigmoid
c: hằng số điều chỉnh dịch chuyển.
tanh: giá trị nằm trong khoảng (-1, 1).
Sigmoid Kernel: là một dạng Kernel phi tuyến đặc biệt trong
SVM sử dụng hàm sigmoid cho phép mô hình tạo ra đường
biên phân loại uốn cong theo hình chữ S ➔phân loại dữ liệu
không thể tách bằng đường thẳng nhưng lại có ranh giới cong
mềm.

93. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oRBF (Radial Basis Function) Kernel: RBF là loại phổ biến nhất trong các bài toán
phân loại với SVM giúp SVM xử lý những bài toán phân loại phi tuyến.
oRBF tạo ra các tổ hợp phi tuyến của các đặc trưng đầu vào ➔ biến đổi dữ liệu từ
không gian ban đầu sang một không gian đặc trưng có chiều cao hơn
oTrong không gian mới này, dữ liệu có thể được phân tách bởi một siêu phẳng
tuyến tính (đường thẳng/phẳng), điều mà không làm được trong không gian ban
đầu

94. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oRBF (Radial Basis Function) Kernel: &#3627408446;(&#3627408485;
1,&#3627408485;
2)=exp−
&#3627408485;
1−&#3627408485;
2
2
2??????
2
oTrong đó: x
1​ ,x
2là hai điểm dữ liệu
•∥x
1​ −x
2∥ Khoảng cách Euclid giữa hai điểm (đo độ giống nhau)
•σĐộ lệch chuẩn –là siêu tham số điều chỉnh "phạm vi ảnh hưởng“
oKhi hai điểm gần nhau → ??????gần 1 → được xem là giống nhau.
oKhi hai điểm xa nhau → K gần 0 → được xem là khác biệt → bị phân
tách.

95. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Thành phần của SVM: Kernel functions
oRBF (Radial Basis Function) Kernel:
Source:ibm.com

96. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Ứng Dụng: SVM được sử dụng rộng rãi trong nhiều lĩnh vực nhờ khả
năng xử lý dữ liệu đa chiều và phi tuyến tính
oNhận diện văn bản: Phân loại văn bản (ví dụ: phân loại cảm xúc trong bài đánh
giá).
oNhận diện hình ảnh: Phân loại ảnh (ví dụ: nhận diện khuôn mặt, phân loại đối
tượng).
oY học: Chẩn đoán bệnh dựa trên dữ liệu y tế (ví dụ: phân loại ung thư dựa trên
đặc trưng sinh học).
oTài chính: Dự đoán rủi ro tín dụng hoặc gian lận tài chính.
Source:ibm.com

97. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Ứng Dụng trong bảo mật:
oPhát hiện sai lệch/Signature Detection: SVM được sử dụng để phát hiện
các mẫu tấn công đã biết (misuse/signature detection) bằng cách phân loại
các đặc trưng mạng (như địa chỉ IP, cổng, giao thức) thành "bình thường"
hoặc "độc hại".
oPhát hiện bất thường (Anomaly Detection): One-class SVM được sử dụng
để phát hiện các mẫu bất thường trong lưu lượng mạng (các cuộc tấn công
chưa biết (zero-day attacks)).
Source:ibm.com

98. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Support Vector Machines (SVM)
▪ Ứng Dụng trong bảo mật:
oPhân loại lưu lượng mạng: SVM được sử dụng để phân loại lưu lượng
mạng thành các loại tấn công cụ thể (như DDoS, probing) hoặc hành vi
bình thường, nhờ khả năng xử lý dữ liệu phi tuyến tính thông qua nhân
RBF.
oPhát hiện phần mềm độc hại (Malware Detection): SVM có thể phân loại
các filethực thi dựa trên đặc trưng tĩnh (như opcode) hoặc động (như hành
vi hệ thống) để xác định phần mềm độc hại
Source:ibm.com

99. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine
▪ Là thuật toán phân loại mạnh mẽ, được mở rộng từ SVM khi bài
toán có nhiều lớp dữ liệu (K > 2 classes)
▪Các phương pháp để mở rộng SVM cho multi-class
oOne-vs-Rest (OvR)
oOne-vs-One (OvO)
Source:ibm.com

100. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine
▪One-vs-Rest (OvR): Với K lớp, xây dựng K bộ phân loại SVM nhị
phân, mỗi bộ phân loại phân tách một lớp với tất cả các lớp còn lại.
▪Quy trình:
oLớp k: Được coi là lớp dương (+1), tất cả các lớp khác là lớp âm (-1).
oHuấn luyện K mô hình SVM riêng biệt.
oDự đoán: Chọn lớp có giá trị hàm quyết định (decision function) cao nhất
▪Ưu điểm: Đơn giản, dễ triển khai, số lượng bộ phân loại ít (K).
▪Nhược điểm: Không tối ưu hóa chung cho tất cả các lớp.

101. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine
▪Ví dụ: Nếu có 3 lớp dữ liệu ➔ sẽ huấn luyện 3 SVM:
oSVM phân loại lớp 1 với lớp còn lại.
oSVM phân loại lớp 2 với lớp còn lại.
oSVM phân loại lớp 3 với lớp còn lại.
▪Khi dự đoán, mô hình sẽ chọn lớp có điểm số cao nhất từ các lớp

102. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine

103. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine
▪One-vs-One (OvO) : Xây dựng một bộ phân loại SVM nhị phân
cho mỗi cặp lớp.
▪ Quy trình: Với K lớp, xây dựng bộ phân loại
oMỗi bộ phân loại phân tách hai lớp i và j.
oDự đoán: Sử dụng bỏ phiếu (voting), lớp nhận được nhiều phiếu nhất được
chọn.
▪Ví dụ: nếu có 3 lớp A, B, C → huấn luyện 3 mô hình: (A, B),
(B,C), (A,C)
&#3627408446;(&#3627408446;−1)
2

104. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine
▪One-vs-One (OvO) :

105. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Multi-class support vector machine
▪Ví dụ : Trong phân loại lưu lượng mạng, giả sử có 4 loại tấn công:
DoS, probe, u2r, r2l
OvR OvO
Xây dựng 4 SVM:
DoS – (proble, u2r, r2l)
probe - (DoS, u2r, r2l)
…
Xây dựng (4*3)/2 = 6 SVM:
-DoS - probe,
-DoS - u2r,
-DoS vs. r2l
-probe – u2r
-probe –r2l
-u2r – r2l

106. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes
▪ Naive Bayes Classification (NBC) là một thuật toán phân loại dựa
trên tính toán xác suất áp dụng định lý Bayes. Thuật toán này thuộc
nhóm Supervised Learning (Học có giám sát).
▪Naive Bayes giả định rằng tất cả các đặc trưng đầu vào đều độc
lập có điều kiện (conditionally independent) với nhau khi biết nhãn
lớp.
Source:ibm.com

107. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes
▪ Định lý Bayes:
▪Trong đó:
oP(C
k|x) xác suất để mẫu thuộc lớp C
kkhi biết đặc trưng x (xác suất hậu nghiệm)
oP(C
k) xác suất của lớp C
ktrước khi có dữ liệu quan sát (xác suất tiên nghiệm)
o??????(&#3627408485;|&#3627408438;
&#3627408472;) xác suất quan sát được đặc trưng x khi biết mẫu thuộc lớp C
k (Hàm
likelihood)
oXác suất của đặc trưng x (thường được bỏ qua vì là hằng số).
??????(&#3627408438;
&#3627408472;|&#3627408485;)=
??????&#3627408438;
&#3627408472;??????(&#3627408485;|&#3627408438;
&#3627408472;)
??????(&#3627408485;)

108. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes
▪ Giả định "naive" (ngây thơ): Các đặc trưng x = (x
1, x
2, …, x
n) độc lập có
điều kiện với nhau khi biết lớp C
k:
▪Quy tắc phân loại: Chọn lớp có xác suất hậu nghiệm cao nhất:
??????(&#3627408485;|&#3627408438;
&#3627408472;)=ෑ
&#3627408470;=1
&#3627408475;
??????(&#3627408485;
&#3627408470;|&#3627408438;
&#3627408472;)
መ&#3627408438;=
&#3627408438;
??????
??????&#3627408479;??????&#3627408474;??????&#3627408485;
??????&#3627408438;
&#3627408472;ෑ
&#3627408470;=1
&#3627408475;
??????(&#3627408485;
&#3627408470;|&#3627408438;
&#3627408472;)

109. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes
▪ Các biến thể của Naïve Bayes:
oGaussian Naive Bayes: Được sử dụng cho các đặc trưng liên tục, giả định
rằng các đặc trưng theo phân phối chuẩn (Gaussian).
&#3627408436;??????(&#3627408485;
&#3627408470;|&#3627408438;
&#3627408472;)=
1
2????????????
&#3627408472;
2
&#3627408466;&#3627408485;&#3627408477;−
&#3627408485;
&#3627408470;−??????
&#3627408472;
2
2??????
&#3627408472;
2
trong đó μlà giá trị kỳ vọng và σlà độ lệch chuẩn của phân phối .

110. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes
▪ Các biến thể của Naïve Bayes:
oMultinomial Naive Bayes: Phù hợp với dữ liệu rời rạc (như tần suất từ
trong văn bản)
oBernoulli Naive Bayes: Được sử dụng khi đặc trưng là nhị phân (vd:mỗi
từ có thể xuất hiện hoặc không xuất hiện trong văn bản)

111. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes - Ứng dụng
▪ Phân loại email (spam / ham)
▪Phân tích cảm xúc (sentiment analysis)
▪Phân loại văn bản, tài liệu
▪Hệ thống đề xuất đơn giản
Source:ibm.com

112. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes - ưu điểm
▪ Naive Bayes có độ phức tạp thấp, phù hợp với dữ liệu lớn và ứng
dụng thời gian thực
▪Không cần điều chỉnh nhiều tham số như SVM ➔ dễ triển khai
▪Naive Bayes hoạt động tốt ngay cả khi số lượng mẫu huấn luyện
hạn chế.
▪Các biến thể (Gaussian, Multinomial, Bernoulli) phù hợp với nhiều
loại đặc trưng.
Source:ibm.com

113. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes - Nhược điểm
▪ Giả định các đặc trưng độc lập thường không đúng trong thực tế (ví dụ:
num_bytes và protocol_type có thể tương quan).
▪Nhạy cảm với dữ liệu mất cân bằng: Các lớp thiểu số có thể bị bỏ qua
nếu không được xử lý đúng.
▪Hiệu suất thấp hơn với dữ liệu phức tạp: So với các mô hình như SVM
hoặc học sâu, Naive Bayes có thể kém chính xác trong các bài toán
không tuyến tính.
➔Xử lý mất cân bằng khi dữ liệu hoặc kết hợp với các mô hình khác
Source:ibm.com

114. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•Naive Bayes - câu hỏi thảo luận
▪ Khi nào nên sử dụng Naive Bayes thay vì các mô hình phức tạp
hơn như SVM hoặc học sâu?
▪Làm thế nào để cải thiện hiệu suất của Naive Bayes trong các bài
toán có tương quan đặc trưng cao?
Source:ibm.com

115. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•k-Nearest Neighbors (k-NN)
▪ k-Nearest Neighbors (k-NN) là một thuật toán học máy đơn giản nhưng mạnh
mẽ, thuộc loại supervised-learning
▪Mô hình không "học" trong giai đoạn huấn luyện mà chỉ "nhớ lại" toàn bộ dữ
liệu huấn luyện và sử dụng dữ liệu đó khi cần dự đoán.
▪Nguyên lý hoạt động:
oKhi nhận một điểm dữ liệu mới, thuật toán k-NN tìm k điểm gần nhất trong tập huấn
luyện.
oDự đoán lớp của điểm dữ liệu mới dựa trên voting (bầu chọn) từ các điểm gần nhất.
ok là số lượng láng giềng gần nhất được xem xét trong quá trình phân loại.
Source:ibm.com

116. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•k-Nearest Neighbors (k-NN): Các bước thực hiện của k-NN
▪ Tính khoảng cách giữa các điểm: Sử dụng Euclidean distance
(hoặc các loại khoảng cách khác như Manhattan, Minkowski) để
tính khoảng cách giữa điểm dữ liệu mới và các điểm trong tập huấn
luyện.
▪Chọn k láng giềng gần nhất: Sắp xếp các điểm trong tập huấn luyện
theo khoảng cách từ điểm dữ liệu mới và chọn ra k điểm gần nhất.
Source:ibm.com
&#3627408472;ℎ&#3627408476;ả&#3627408475;&#3627408468; &#3627408464;á&#3627408464;ℎ &#3627408440;&#3627408482;&#3627408464;&#3627408473;??????&#3627408465;&#3627408466;&#3627408462;&#3627408475;=෍
&#3627408470;=1
&#3627408475;
&#3627408485;
&#3627408470;−&#3627408486;
&#3627408470;
2

117. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•k-Nearest Neighbors (k-NN): Các bước thực hiện của k-NN
▪ Dự đoán lớp:
oPhân loại (Classification): Lớp của điểm dữ liệu mới được dự đoán bằng
cách bầu chọn lớp xuất hiện nhiều nhất trong k láng giềng gần nhất.
oHồi quy (Regression): Dự đoán là giá trị trung bình của các giá trị mục tiêu
(target values) của k láng giềng gần nhất.

118. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•k-Nearest Neighbors (k-NN)
▪ Ưu điểm:
oĐơn giản và dễ hiểu.
oKhông cần giả thuyết về phân phối dữ liệu (non-parametric).
oHoạt động tốt trong các bài toán với tập dữ liệu nhỏ và vừa.
▪Nhược điểm:
oTính toán chậm trong giai đoạn phân loại, đặc biệt khi tập huấn luyện lớn.
oYêu cầu bộ nhớ lớn vì phải lưu toàn bộ dữ liệu huấn luyện.
oDễ bị ảnh hưởng bởi dữ liệu nhiễu và không thích hợp với dữ liệu quá lớn .
oPhụ thuộc vào k: Giá trị k không phù hợp có thể dẫn đến overfitting (k quá nhỏ)
hoặc underfitting (k quá lớn).

119. https://huit.edu.vn
Các kỹ thuật phân lớp dữ liệu
•k-Nearest Neighbors (k-NN)
▪ Ứng dụng:
o Phân loại hành vi hoặc lưu lượng mạng là bình thường hay bất thường.
oPhân loại văn bản: Phân loại email, tài liệu hoặc các văn bản vào các lớp
khác nhau (ví dụ, spam hoặc không spam).
oNhận dạng mẫu và phân loại ảnh: Phân loại ảnh hoặc nhận dạng chữ viết
tay dựa trên các mẫu dữ liệu gần nhất.
o Sử dụng trong phát hiện các cuộc tấn công hoặc hành vi bất thường trong
các hệ thống mạng.

120. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
Partitioning
Methods)
K-means
Clustering
K-medoids
Clustering

121. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering: là một thuật toán học không giám sát
(unsupervised learning) thuộc nhóm phương pháp phân hoạch
(partitioning methods) trong kỹ thuật gom nhóm (clustering).
▪Mục tiêu của thuật toán là:
oChia n điểm dữ liệu thành k cụm (clusters), mỗi cụmđược đại diện bởi
một centroid (trung tâm)
oMỗi điểm dữ liệu sẽ được phân vào cụmcó centroid gần nhất.
oCentroid của một cụm là trung bình của các điểm dữ liệu trong cụm đó.

122. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering

123. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering: hàm mục tiêu
▪Trong đó:
ox
i: Điểm dữ liệu thứ i.
oμ
k​: Tâm của cụm thứ k.
or
ik: Chỉ số nhị phân, bằng 1 nếu điểm x
i thuộc cụm k, bằng 0 nếu không.
o&#3627408485;
&#3627408470;−??????
&#3627408472;
2
: Bình phương khoảng cách Euclidean giữa điểm x
i​ và tâm cụm μ
k
&#3627408445;=෍
&#3627408470;=1
&#3627408475;
෍
&#3627408472;=1
??????
&#3627408479;
&#3627408470;&#3627408472;&#3627408485;
&#3627408470;−??????
&#3627408472;
2
Thuật toán tìm cách tối thiểu hóa
hàm mục tiêu J bằng cách lặp lại
việc gán các điểm vào cụm và cập
nhật tâm cụm.

124. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering:
oB1- Khởi tạo: Chọn số lượng cụm K, lựa chọn ngẫu nhiên K điểm dữ liệu
làm centroids ban đầu. Mỗi centroid sẽ đại diện cho một nhóm.
oB2- Gán nhãn cụm: Mỗi điểm dữ liệu được gán vào cụm có tâm gần nhất,
dựa trên khoảng cách Euclidean
oB3- Cập nhật tâm cụm: Tính lại tâm cụm bằng trung bình của tất cả các
điểm thuộc cụm đó
oLặp lại bước 2 và 3 cho đến khi centroids không thay đổi nữa.
&#3627408479;
&#3627408470;&#3627408472;=ቐ
1 &#3627408475;ế&#3627408482; &#3627408472;=&#3627408462;&#3627408479;&#3627408468;&#3627408474;??????&#3627408475;
&#3627408471;&#3627408485;
&#3627408470;−??????
&#3627408471;
2
0 &#3627408475;ế&#3627408482; &#3627408475;&#3627408468;ượ&#3627408464; &#3627408473;ạ??????
&#3627408436;??????
&#3627408472;=
1
&#3627408475;
&#3627408472;
෍
&#3627408485;
??????∈&#3627408438;
??????
&#3627408485;
&#3627408470;cụmC
kgồmn
kđiểm dữ liệu

125. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering:
o Ưu điểm:
•Đơn giản và dễ triển khai
•Dễ dàng triển khai: Thuật toán có thể dễ dàng được triển khai trên nhiều ngôn ngữ lập
trình
oNhược điểm
•Phụ thuộc vào giá trị K
•Việc chọn các centroid ban đầu có thể ảnh hưởng đến kết quả cuối cùng
•Không hiệu quả với các nhóm có hình dạng phức tạp

126. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering:
oỨng dụng:
• K-means được dùng để xác định các mẫu bất thường trong lưu lượng mạng, ví dụ
như phát hiện các kết nối bất thường hoặc tấn công mạng
•K-means được sử dụng để phân cụm dữ liệu trước khi áp dụng các kỹ thuật bảo vệ
quyền riêng tư, đảm bảo dữ liệu nhạy cảm được ẩn đi mà vẫn giữ được cấu trúc cụm
•K-means phân cụm khách hàng dựa trên hành vi mua sắm, giúp tối ưu hóa chiến lược
tiếp thị
•Xử lý ảnh và nén dữ liệu
•..

127. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-means Clustering: Bài tập
oCho tập hợp các điểm dữ liệu 2 chiều sau:
{(1,2),(2,3),(3,3),(8,8),(9,9),(10,10)}
oHãy áp dụng K-means để chia tập dữ liệu trên thành K=2 nhóm

128. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-medoids Clustering: K-medoids clustering là một phương pháp
phân cụm trong học máy tương tự như thuật toán K-means
▪K-medoids chọn một điểm dữ liệu thực tế trong cụm làm đại diện,
được gọi là medoid
▪Medoid là điểm có tổng khoảng cách đến tất cả các điểm khác
trong cụm là nhỏ nhất

129. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-medoids Clustering:
oHàm mục tiêu
ox
i: Điểm dữ liệu thứ i.
om
k​: Medoid của cụm thứ k.
or
ik: Chỉ số nhị phân, bằng 1 nếu điểm x
i thuộc cụm k, bằng 0 nếu không.
o&#3627408485;
&#3627408470;−&#3627408474;
&#3627408472;: Khoảng cách Euclidean giữa điểm x
i​ và medoidm
k
&#3627408445;=෍
&#3627408470;=1
&#3627408475;
෍
&#3627408472;=1
??????
&#3627408479;
&#3627408470;&#3627408472;&#3627408485;
&#3627408470;−&#3627408474;
&#3627408472;
Mục tiêu của K-medoids là tối
thiểu hóa tổng khoảng cách
(thường là tuyệt đối hoặc bình
phương) từ các điểm đến medoid
của cụm tương ứng.

130. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-medoids Clustering: Thuật toán
oB1- Khởi tạo: Chọn số lượng cụm k. Chọn ngẫu nhiên k điểm dữ liệu làm
medoid ban đầu
oB2- Gán nhãn dữ liệu: Gán mỗi điểm dữ liệu vào cụm có medoid gần nhất, dựa
trên khoảng cách
oB3-Cập nhật medoid: Tính lại medoid của mỗi nhóm. Medoid mới được chọn là
điểm dữ liệu thực tế trong nhóm có tổng khoảng cách nhỏ nhất đến tất cả các
điểm trong nhóm.
oLặp lại bước 2 và bước 3 cho đến khi các medoid không thay đổi hoặc thay đổi
rất ít

131. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-medoids Clustering:
oƯu điểm
•Vì sử dụng medoid (điểm dữ liệu thực tế) thay vì trung bình, K-medoids ít bị ảnh
hưởng bởi các giá trị ngoại lệ
oNhược điểm:
•Chi phí tính toán cao hơn K-means: Việc tìm medoid tối ưu cho mỗi nhóm có thể tốn
thời gian tính toán, đặc biệt khi số lượng điểm dữ liệu lớn.
•Yêu cầu xác định trước số cụm k, có thể dẫn đến kết quả không tối ưu nếu chọn sai

132. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân hoạch
▪ K-medoids Clustering: Ứng dụng
oPhân nhóm khách hàng
oPhân đoạn ảnh
oPhân nhóm tài liệu văn bản
oPhát hiện bất thường
o...

133. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Hierarchical Clustering là một phương pháp phân cụm không giám
sát, trong đó các điểm dữ liệu được nhóm lại dựa trên mức độ
tương đồng (khoảng cách Euclidean hoặc Jaccard…).
▪Phương pháp này xây dựng một câyphân cấp (dendrogram), trong
đó các điểm dữ liệu được hợp nhất hoặc chia tách để tạo thành các
cụm.

134. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Câyphân cấp (dendrogram): là biểu đồ cây mô tả quá trình các
cụm được gộp hoặc tách dần theo mức độ tương đồng.
oGốc cây: từng điểm dữ liệu riêng lẻ.
oCàng lên cao: các cụm lớn hơn.
oĐộ cao nhánh: thể hiện độ khác biệt giữa các cụm (nhánh càng thấp →
cụm càng giống nhau).

135. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Câyphân cấp (dendrogram):
Kdnuggets.com

136. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Phân loại:
oAgglomerative Hierarchical Clustering (Phân nhóm từ dưới lên) ➔ phổ
biến hơn
oDivisive Clustering (từ trên xuống)

137. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Agglomerative Hierarchical Clustering (Phân nhóm từ dưới lên)
oBắt đầu với mỗi điểm dữ liệu là một
cụm riêng lẻ.
oLặp lại quá trình hợp nhất hai cụm gần
nhau nhất (dựa trên một thước đo
khoảng cách) cho đến khi tất cả các
điểm được gộp vào một cụm duy nhất.
oKết quả là một dendrogram, biểu diễn
các cụm ở các mức độ tương đồng
khác nhau.
builtin.com

138. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Divisive Clustering (từ trên xuống)
oBắt đầu với tất cả các điểm dữ liệu
trong một cụm duy nhất.
oLặp lại quá trình chia cụm lớn thành
các cụm nhỏ hơn dựa trên sự khác biệt
giữa các điểm dữ liệu.
oCách tiếp cận này ít phổ biến hơn
Agglomerative.
▪Divisive Clustering (từ trên xuống)
builtin.com

139. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Các phương pháp đo khoảng cách giữa hai cụm
oSingle Linkage: Khoảng cách giữa hai cụm là khoảng cách nhỏ nhất giữa
bất kỳ cặp điểm nào thuộc hai cụm.
oComplete Linkage: Khoảng cách giữa hai cụm là khoảng cách lớn nhất
giữa bất kỳ cặp điểm nào thuộc hai cụm.
oAverage Linkage: Khoảng cách giữa hai cụm là trung bình của tất cả các
khoảng cách giữa các cặp điểm thuộc hai cụm.
builtin.com

140. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Đo khoảng cách xác định độ tương đồng giữa các điểm dữ liệu
o Khoảng cách Euclidean: Đo lường khoảng cách thẳng giữa hai điểm trong
không gian đa chiều
oKhoảng cách Jaccard: thường dùng trong phân cụm, phân loại và xử lý văn
bản, đặc biệt khi dữ liệu là nhị phân hoặc rời rạc
&#3627408465;(&#3627408485;,&#3627408486;)=෍
&#3627408470;=1
&#3627408475;
&#3627408485;
&#3627408470;−&#3627408486;
&#3627408470;
2
x và y là hai điểm dữ liệu,
và n là số chiều.
Độ tương đồng Jaccard&#3627408445;(&#3627408436;,&#3627408437;)=
&#3627408436;∩&#3627408437;
&#3627408436;∪&#3627408437;
Khoảng cách Jaccard được tính là 1−J(A,B).

141. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Ưu điểm:
oKhông cần biết trước số lượng cluster
oDễ dàng trực quan hóa
oPhù hợp với các bài toán có cấu trúc phân cấp tự nhiên
▪Nhược điểm:
oHiệu suất tính toán thấp với dữ liệu lớn

142. https://huit.edu.vn
Các kỹ thuật gom nhóm
•Phương pháp phân cấp (Hierarchical Clustering)
▪ Ứng dụng
oPhát hiện tài khoản giả mạo: Các tài khoản giả mạo hoặc bot thường có các
mẫu hành vi tương tự (ví dụ: tần suất đăng nhập bất thường, sử dụng cùng
một tập hợp cookie, hoặc truy cập vào các tên miền đáng ngờ) ➔ nhóm
các tài khoản này thành các cụm dựa trên các đặc điểm trên
oXác định các mẫu quét bất thường bằng cách nhóm các kết nối mạng dựa
trên các đặc điểm như địa chỉ IP đích, cổng, và tần suất quét ➔ điều tra
nguồn gốc của các cuộc tấn công.

143. https://huit.edu.vn
Các kỹ thuật gom nhóm
• Câu hỏi thảo luận:
▪Trong những trường hợp nào sẽ sử dụng K-means thay vì
Hierarchical Clustering?
▪Phương pháp gom nhóm nào phù hợp nhất khi làm việc với các tập
dữ liệu lớn?