hocmay co ban tham khao ban demo phan loai

demo phanloai cho sinh vien co ban tham khao

1. LỜI CẢM ƠN
Lời đầu tiên cho phép nhóm chúng em gửi lời cám ơn sâu sắc tới thầy cô đã
truyền đạt những kiến thức và viết thành giáo trình để chúng em có cơ hội học
tập. Đó là những kiến thức quý báu và bổ ích. Để hoàn thành được bài tập lớn
này, đặc biệt nhóm chúng em xin được bày tỏ sự tri ân và chân thành cảm ơn
giảng viên người trực tiếp hướng dẫn, chỉ bảo nhóm chúng em trong suốt quá
trình học tập và nghiên cứu để hoàn thành bài tập lớn này. Nhờ có sự giúp đỡ
của thầy nhóm chúng em đã có thể hoàn thành bài tập một cách tốt nhất và đạt
được những kết quả khả quan.
Trong quá trình nghiên cứu và làm báo cáo do năng lực, kiến thức còn hạn hẹp
nên không tránh khỏi những thiếu sót. Nhóm chúng em kính mong nhận được
sự thông cảm và những ý kiến đóng góp của quý thầy cô và các bạn.
Một lần nữa, em xin chân thành cảm ơn thầy/cô vì sự hỗ trợ và đóng góp của
mình trong quá trình thực hiện bài tập lớn này.
Nhóm em xin chân thành cảm ơn!
LỜI MỞ ĐẦU
Machine Learning là một lĩnh vực của trí tuệ nhân tạo nghiên cứu và phát triển
các thuật toán và mô hình để giúp máy tính học hỏi từ dữ liệu một cách tự động
và cải thiện hiệu suất theo thời gian. Học máy có rất nhiều ứng dụng trong các
lĩnh vực như y tế, tài chính, marketing, công nghệ thông tin và nhiều lĩnh vực
khác.
Tìm hiểu thuật toán KNN và ứng dụng cho bài toán phân loại sản phẩm là một
chủ đề rất thú vị và hấp dẫn trong lĩnh vực Machine Learning. Thuật toán KNN
(K-Nearest Neighbors) là một trong những thuật toán phân loại đơn giản và hiệu
quả nhất trong Machine Learning. Thuật toán này dựa trên nguyên lý rằng các
điểm dữ liệu có các đặc trưng tương tự sẽ nằm gần nhau trong không gian đặc
trưng. Trong bài toán phân loại rượu, chúng ta có một tập dữ liệu chứa thông tin
về các loại sản phẩm và nhãn cho biết chúng thuộc loại sản phẩm nào. Chúng ta

2. có thể sử dụng thuật toán K-Nearest Neighbors (KNN) để phân loại các loại sản
phẩm dựa trên các đặc trưng của chúng.
Chương 1 của bài tập lớn này sẽ giới thiệu cơ sở lý thuyết của Machine
Learning, bao gồm các khái niệm cơ bản như supervised learning, unsupervised
learning,.... Ngoài ra, chương này cũng sẽ giới thiệu về bài toán phân loại và các
phương pháp tiếp cận khác nhau để giải quyết bài toán này.
Chương 2 sẽ tập trung vào thuật toán KNN và các quy trình của nó vào bài toán
phân loại sản phẩm. Chúng em tìm hiểu cách thuật toán KNN hoạt động, các
tham số quan trọng của thuật toán và cách lựa chọn giá trị tối ưu cho các tham
số này và lấy ví dụ về thuật toán KNN.
Chương 3 sẽ trình bày về quá trình thử nghiệm của chúng em trên tập dữ liệu
rượu. Chúng em sẽ đánh giá hiệu suất của thuật toán KNN trên tập dữ liệu này
và tính độ chính xác của tập dữ liệu.
Qua bài tập lớn này, nhóm chúng em đã có cơ hội tìm hiểu sâu hơn về thuật
toán KNN và các ứng dụng của nó trong bài toán phân loại sản phẩm. Chúng
em cũng sẽ có thể áp dụng các kiến thức đó để giải quyết các bài toán phân loại
khác trong
Machine Learning.
CHƯƠNG 1. TỔNG QUAN VỀ HỌC MÁY
1.1 Đặt vấn đề
Những năm gần đây, AI nổi lên như một bằng chứng của cuộc cách mạng công
nghiệp lần thứ tư. Trí tuệ nhân tạo có thể được định nghĩa như một nghành của
khoa học máy tính liên quan đến việc tự động hóa các hành vi thông minh. Theo
đà phát triển của công nghệ, ứng dụng trí tuệ nhân tạo luôn là xu hướng công
nghệ tương lai mà các hãng công nghệ trên toàn thế giới đua nhau sáng tạo, nó
là nền tảng cốt lõi của cuốc cách mạng công nghệ 4.0.
MI (Machine Learning) là một lĩnh vực của trí tuệ nhân tạo được sinh ra từ ML
(Machine Learning) là một lĩnh vực của trí tuệ nhân tạo, được sinh ra từ khả
năng nhận diện mẫu và từ lý thuyết các máy tính có thể học mà không cần phải
lập trình để xử lý các nhiệm vụ cụ thể nào đó.

3. Các ứng dụng của ML đã quá quen thuộc với con người: xe tự hành của Google
và Tesla, hệ thống tự tag khuôn mặt trên Facebook, hệ thống gợi ý sản phẩm
của Amazon, hệ thống gợi ý phim của Netflix..., chỉ là một vài trong vô vàn
những ứng dụng của trí tuệ nhân tạo và cụ thể là ML.
Hình 1 : Mối quan hệ gin Al, Machine Learning và Deep Learning
Xu hướng phát triển công nghệ thông tin ngày càng tăng, song song với nó
lượng dữ liệu được sinh ra cũng ngày một lớn. Vì vậy nhu cầu để xử lý dữ liệu
cũng lớn hơn, ML đang góp phần giải quyết vấn đề này. Một trong những thuật
toán thường dùng trong ML đó là thuật toán K- nearest neighbor (KNN). Ứng
dụng của thuật toán này được sử dụng rất nhiều và rộng rãi trong các bài toán
phân lớp. Cụ thể thì trong bài tập lớn này nhóm chúng em sẽ ứng dụng thuật
toán KNN vào bài toán phân loại sản phẩm.
Để áp dụng thuật toán KNN cho bài toán phân loại sản phẩm, chúng ta cần xác
định các đặc trưng quan trọng để phân loại. Các đặc trưng này có thể bao gồm
Khi đã xác định các đặc trưng, chúng ta sẽ sử dụng tập dữ liệu huấn luyện để
huấn luyện mô hình KNN. Sau đó, chúng ta sẽ sử dụng mô hình đã huấn luyện
để phân loại các loại sản phẩm mới dựa trên các đặc trưng của chúng.
Tóm lại, thuật toán KNN là một trong những thuật toán phổ biến trong Machine
Learning được sử dụng để phân loại dữ liệu dựa trên khoảng cách giữa chúng và
các điểm dữ liệu trong tập huấn luyện. Áp dụng thuật toán KNN cho bài toán
phân loại sản phẩm có thể giúp chúng ta phân loại các sản phẩm mới dựa trên
các đặc trưng của chúng.
1.2 Machine Learning là gì?
Machine Learning (hay học máy) là một lĩnh vực của trí tuệ nhân tạo (AI) mà
nghiên cứu cách để máy tính học hỏi từ dữ liệu mà không cần được lập trình

4. một cách cụ thể. Thay vì chỉ đơn giản là thực hiện các chỉ thị được lập trình
trước đó, máy tính được lập trình để tìm ra các mô hình và kết luận từ dữ liệu
đầu vào.
Machine Learning được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau, bao
gồm kinh doanh, y học, khoa học dữ liệu, thị giác máy tính, xử lý ngôn ngữ tự
nhiên, và robot học. Với sự phát triển của công nghệ và dữ liệu, Machine
Learning đang trở thành một công cụ quan trọng để giải quyết các vấn đề và tạo
ra giá trị mới trong nhiều lĩnh vực.
1.3. Các phương pháp Machine Learning
1.3.1 Supervised machine learning
Supervised learning còn được gọi là học máy có giám sát, được định nghĩa bằng
cách sử dụng các tập dữ liệu được gắn nhãn để huấn luyện các thuật toán phân
loại dữ liệu hoặc dự đoán kết quả một cách chính xác.
Khi dữ liệu đầu vào được đưa vào mô hình, mô hình sẽ điều chỉnh trọng lượng
của nó cho đến khi nó được lắp một cách thích hợp. Điều này xảy ra như một
phần của quá trình xác nhận chéo để đảm bảo rằng mô hình tránh trang bị quá
nhiều hoặc trang bị thiếu thông tin.
Supervised machine learning giúp các tổ chức giải quyết nhiều vấn đề trong thế
giới thực trên quy mô lớn, chẳng hạn như phân loại thư rác trong một thư mục
riêng biệt từ hộp thư đến của bạn.
Một số phương pháp được sử dụng trong Supervised machine learning bao
gồm: logistic regression, neural networks, linear regression, naive bayes,
random forest, và support vector machine (SVM).
1.3.2 Unsupervised machine learning
Unsupervised machine learning là phương pháp sử dụng các thuật toán máy học
để phân tích và phân cụm các tập dữ liệu không được gắn nhãn. Không cần sự
can thiệp của con người, các thuật toán này có thể phát hiện ra các mẫu hoặc
nhóm dữ liệu ẩn. Khả năng phát hiện ra những điểm tương đồng và khác biệt
trong thông tin của phương pháp này khiến nó trở nên lý tưởng cho việc phân

5. tích dữ liệu khám phá, chiến lược bán chéo (cross-sell), phân khúc khách hàng
cũng như nhận dạng hình ảnh và mẫu.
Unsupervised machine learning cũng được sử dụng để giảm số lượng các tính
năng trong một mô hình thông qua quá trình giảm kích thước. Phân tích thành
phần chính (PCA) và phân tích giá trị đơn lẻ (SVD) là hai cách tiếp cận phổ
biến cho việc này.
Các thuật toán khác được sử dụng trong học tập không giám sát bao gồm: k-
means clustering, neural networks, và probabilistic clustering methods. 1.3.3
Semi-supervised learning
Semi-supervised learning cung cấp một phương pháp hiệu quả giữa học tập có
giám sát và không giám sát. Trong quá trình đào tạo, nó sử dụng một tập dữ liệu
có nhãn nhỏ hơn để hướng dẫn phân loại và trích xuất tính năng từ một tập dữ
liệu lớn hơn, không được gắn nhãn.
Phương pháp Semi-supervised learning có thể giải quyết vấn đề không có đủ dữ
liệu được gắn nhãn cho thuật toán học có giám sát. Nó cũng hữu ích nếu quá tốn
kém để gắn nhãn đủ dữ liệu.
1.4 CÁC THUẬT TOÁN PHỔ BIẾN CỦA MACHINE LEARNING

Neural networks: Mô phỏng cách thức hoạt động của bộ não con người, với
một số lượng khổng lồ các nút xử lý được liên kết. Neural networks là thuật
toán được dùng trong việc nhận dạng các mẫu và đóng một vai trò quan trọng
trong các ứng dụng bao gồm dịch ngôn ngữ tự nhiên, nhận dạng hình ảnh, nhận
dạng giọng nói và tạo hình ảnh.


Linear regression: Thuật toán này được sử dụng để dự đoán các giá trị số, dựa
trên mối quan hệ tuyến tính giữa các giá trị khác nhau.


Logistic regression: Thuật toán giúp đưa ra dự đoán cho các biến phản hồi
phân loại, chẳng hạn như câu trả lời “có/không” cho các câu hỏi. Nó có thể
được sử dụng cho các ứng dụng như phân loại thư rác và kiểm soát chất lượng
trên dây chuyền sản xuất.


Clustering: Các thuật toán phân cụm có thể xác định các mẫu trong dữ liệu để
nó có thể được nhóm lại. Máy tính có thể giúp các nhà khoa học dữ liệu bằng
cách xác định sự khác biệt giữa các mục dữ liệu mà con người đã bỏ qua.

6. 
Decision trees: Là thuật toán được sử dụng để dự đoán giá trị số (hồi quy) và
phân loại dữ liệu. Decision trees sử dụng một chuỗi phân nhánh của các quyết
định được liên kết có thể được biểu diễn bằng sơ đồ cây. Một trong
những ưu điểm của decision trees là chúng dễ xác thực và kiểm tra, không giống
thuật toán Neural networks.


Random forests: Trong một khu rừng ngẫu nhiên, thuật toán máy học dự
đoán một giá trị hoặc danh mục bằng cách kết hợp các kết quả từ một số cây
quyết định.
1.5 ỨNG DỤNG THỰC TẾ CỦA MACHINE LEARNINGS Một số ứng
dụng thực tế của Machine Learning như:


Speech recognition: Dùng để nhận dạng giọng nói tự động (ASR), nhận dạng
giọng nói máy tính hoặc chuyển giọng nói thành văn bản. Đây là một khả năng
sử dụng xử lý ngôn ngữ tự nhiên (NLP) để dịch giọng nói của con người sang
định dạng viết.


Customer service: Chatbots trực tuyến đang thay thế các tác nhân con người
trong hành trình của khách hàng, thay đổi cách chúng ta nghĩ về sự tương tác
của khách hàng trên website và nền tảng xã hội.


Computer vision: Công nghệ AI này cho phép máy tính lấy thông tin có ý
nghĩa từ video, hình ảnh kỹ thuật số và các đầu vào trực quan khác, sau đó thực
thi hành động thích hợp.


Recommendation engines: Sử dụng dữ liệu hành vi tiêu dùng trong quá khứ,
các thuật toán AI learning có thể giúp khám phá các xu hướng dữ liệu có thể
được sử dụng để phát triển các chiến lược cross-sell hiệu quả hơn.


Automated stock trading: Được thiết kế để tối ưu hóa danh mục đầu tư chứng
khoán, các nền tảng giao dịch tần suất cao do AI điều khiển để hàng triệu giao
dịch mỗi ngày mà không cần đến sự can thiệp của con người.


Fraud detection: Các ngân hàng và các tổ chức tài chính có thể sử dụng máy
học để phát hiện các giao dịch đáng ngờ.

7. CHƯƠNG 2: BÀI TOÁN VÀ PHƯƠNG PHÁP SỬ DỤNG
Các thuật toán có thể sử dụng cho bài toán phân loại sản phẩm
Có nhiều thuật toán khác nhau để giải quyết bài toán phân loại sản phẩm, tuy
nhiên một số thuật toán phổ biến bao gồm:
1. Decision Tree: thuật toán xây dựng một cây quyết định dựa trên các thuộc
tính của dữ liệu đầu vào, từ đó phân loại các mẫu dữ liệu.
2. Random Forest: thuật toán kết hợp nhiều cây quyết định để tạo ra một mô
hình phân loại chính xác hơn
3. K-Nearest Neighbors (KNN): thuật toán dựa trên việc tìm kiếm các điểm dữ
liệu gần nhất với điểm dữ liệu đang xét để phân loại.
4. Naive Bayes: thuật toán dựa trên định lý Bayes để tính xác suất của từng lớp
và phân loại mẫu dữ liệu mới dựa trên xác suất cao nhất.
5. Support Vector Machine (SVM): thuật toán tìm ra một siêu phẳng tốt nhất để
phân chia các lớp dữ liệu
Và trong bài toán phân loại rượu này nhóm chúng em sử dụng thuật toán K
nearest neighbor hay KNN để phân loại tính toán từng loại rượu và tính độ
chính xác của bài toán.
2.1. THUẬT TOÁN DECISION TREE
Thuật toán Decision Tree là một thuật toán học có giám sát được sử dụng để
phân loại hoặc dự đoán giá trị của một biến mục tiêu dựa trên các thuộc tính đầu
vào. Đầu tiên, thuật toán sẽ xây dựng một cây quyết định bằng cách chia tập dữ
liệu thành các tập con dựa trên các thuộc tính của chúng. Mỗi nút trên cây đại
diện cho một thuộc tính và mỗi cạnh đại diện cho một giá trị của thuộc tính đó.
2.1.1 Xây dựng cây quyết định
1. Chọn thuộc tính tốt nhất để chia tập dữ liệu ban đầu thành các tập con. Một
số phương pháp để chọn thuộc tính tốt nhất bao gồm Information Gain, Gain
Ratio và Gini Index.

8. 2. Chia tập dữ liệu ban đầu thành các tập con dựa trên giá trị của thuộc tính
được chọn.
3. Lặp lại quá trình trên với các tập con mới cho đến khi các tập con chỉ còn
chứa các mẫu dữ liệu thuộc cùng một lớp hoặc không còn thuộc tính nào để
chia.
2.1.2 Phân loại mẫu dữ liệu mới
Khi cây quyết định đã được xây dựng, ta có thể sử dụng nó để phân loại mẫu dữ
liệu mới bằng cách đi từ gốc của cây đến lá tương ứng với mẫu dữ liệu đó. Mỗi
nút trên cây đại diện cho một thuộc tính và giá trị của nó, ta sẽ di chuyển xuống
theo cạnh tương ứng với giá trị của thuộc tính của mẫu dữ liệu mới. Khi đến lá,
ta sẽ phân loại mẫu dữ liệu mới vào lớp tương ứng với lá đó.
2.1.3 Ưu điểm và nhược điểm
Ưu điểm:
- Dễ hiểu và giải thích
- Có khả năng xử lý các tập dữ liệu lớn
- Có khả năng xử lý các thuộc tính số hoặc rời rạc
Nhược điểm:
- Dễ bị quá khớp khi cây quyết định quá phức tạp
- Không thể xử lý được các thuộc tính liên tục
- Không phù hợp cho các bài toán có số lượng lớn các lớp dữ liệu khác nhau.
2.2 THUẬT TOÁN RANDOM FOREST
Thuật toán Random Forest là một thuật toán học có giám sát được sử dụng để
phân loại hoặc dự đoán giá trị của một biến mục tiêu dựa trên các thuộc tính đầu
vào. Nó là một phương pháp kết hợp nhiều cây quyết định để tạo ra một mô
hình phân loại chính xác hơn.
2.2.1 Xây dựng Random Forest
1. Chọn ngẫu nhiên một tập con các mẫu dữ liệu từ tập dữ liệu ban đầu.

9. 2. Xây dựng một cây quyết định trên tập con dữ liệu được chọn. Khi xây dựng
cây, ta chỉ chọn ngẫu nhiên một số thuộc tính để xem xét khi tìm kiếm thuộc
tính tốt nhất để chia tập dữ liệu.
3. Lặp lại quá trình trên để xây dựng nhiều cây quyết định khác nhau. 4. Khi có
một mẫu dữ liệu mới cần phân loại, ta cho mỗi cây quyết định trả về kết quả
phân loại của nó. Kết quả cuối cùng được tính toán bằng cách chọn lớp có số
phiếu bầu (votes) cao nhất.
2.2.2 Ưu điểm và nhược điểm của Random Forest
Ưu điểm:
1. Tính ổn định: Random Forest có khả năng giảm thiểu overfitting, tức là mô
hình không chỉ tốt trên tập huấn luyện mà còn tốt trên tập kiểm tra. 2. Tính linh
hoạt: Random Forest có thể được sử dụng cho cả bài toán phân loại và dự đoán.
3. Tính khả diễn giải: Random Forest có thể cung cấp thông tin về sự quan trọng
của các thuộc tính đầu vào trong việc phân loại.
Nhược điểm:
1. Tốc độ huấn luyện: Do phải xây dựng nhiều cây quyết định, việc huấn luyện
Random Forest có thể mất nhiều thời gian hơn so với các thuật toán khác.
2. Tính phức tạp: Random Forest có nhiều siêu tham số cần được điều chỉnh để
đạt hiệu suất tốt nhất, điều này có thể khiến cho việc sử dụng thuật toán này trở
nên phức tạp hơn so với các thuật toán khác.
2.3 THUẬT TOÁN K-NEAREST NEIGHBORS (KNN)
Thuật toán K-Nearest Neighbors (KNN) là một thuật toán học có giám sát được
sử dụng để phân loại hoặc dự đoán giá trị của một biến mục tiêu dựa trên các
thuộc tính đầu vào. Nó dựa trên việc tìm ra các điểm dữ liệu gần nhất với mẫu
dữ liệu cần phân loại và dựa trên chúng để đưa ra dự đoán.
2.3.1 Xây dựng KNN

10. 
Chọn giá trị K, tức là số lượng điểm dữ liệu gần nhất cần được sử
dụng để đưa ra dự đoán.


Tính khoảng cách giữa mẫu dữ liệu mới và tất cả các điểm dữ liệu
trong tập huấn luyện.


Chọn K điểm dữ liệu gần nhất với mẫu dữ liệu mới.


Đối với bài toán phân loại, ta đếm số lượng điểm dữ liệu trong K
điểm gần nhất của mẫu dữ liệu mới thuộc vào từng lớp và chọn lớp
có số lượng điểm dữ liệu nhiều nhất là kết quả phân loại.


Đối với bài toán dự đoán, ta tính trung bình giá trị của K điểm gần
nhất để đưa ra dự đoán.
2.3.2 Ưu điểm và nhược điểm của KNN
Ưu điểm


Dễ hiểu và triển khai: KNN là một thuật toán đơn giản và không yêu
cầu nhiều giả định về dữ liệu.


Khả năng phân loại tốt cho các tập dữ liệu phức tạp: KNN hoạt động
tốt trên các tập dữ liệu có tính phức tạp cao.
Nhược điểm


Tính toán phức tạp: KNN có thể yêu cầu thời gian và tài nguyên tính
toán lớn để tìm kiếm các điểm
2.4 THUẬT TOÁN NAIVE BAYES
Thuật toán Naive Bayes là một thuật toán học có giám sát được
sử dụng để phân loại hoặc dự đoán giá trị của một biến mục tiêu dựa
trên các thuộc tính đầu vào. Nó dựa trên định lý Bayes để tính xác suất
của từng lớp và phân loại mẫu dữ liệu mới dựa trên xác suất cao nhất.
2.4.1 Xây dựng Naive Bayes

11. 1. Tính xác suất của từng lớp dựa trên tập huấn luyện. Để tính xác suất
của một lớp, ta đếm số lần mỗi lớp xuất hiện trong tập huấn luyện
và chia cho tổng số mẫu dữ liệu trong tập huấn luyện.
2. Tính xác suất của từng thuộc tính dựa trên tập huấn luyện. Để tính
xác suất của một thuộc tính, ta đếm số lần thuộc tính đó xuất hiện
trong các mẫu dữ liệu của từng lớp và chia cho tổng số mẫu dữ liệu
trong từng lớp.
3. Tính xác suất của một mẫu dữ liệu mới thuộc về từng lớp bằng cách
áp dụng định lý Bayes. Để tính xác suất này, ta nhân các xác suất
của từng thuộc tính trong mẫu dữ liệu với nhau và nhân kết quả với
xác suất của lớp. Lớp có xác suất cao nhất sẽ được chọn là kết quả
phân loại.
2.4.2 Ưu điểm của Naive Bayes
1. Tính đơn giản: Naive Bayes là một thuật toán đơn giản và nhanh
chóng để triển khai.
2. Hiệu suất tốt: Naive Bayes thường cho kết quả phân loại tốt trên các
tập dữ liệu lớn và có nhiều thuộc tính.
3. Khả năng xử lý dữ liệu thiếu: Naive Bayes có thể xử lý các mẫu dữ
liệu bị thiếu giá trị cho một số thuộc tính bằng cách bỏ qua thuộc
tính đó trong quá trình tính toán xác suất.
2.4.3 Nhược điểm của Naive Bayes
1. Giả định về tính độc lập giữa các thuộc tính: Naive Bayes giả
định rằng các thuộc tính là độc lập với nhau, điều này có thể không
đúng trong thực tế. 2. Không hiệu quả khi số lượng mẫu dữ liệu
nhỏ: Naive Bayes có thể không
hiệu quả khi số lượng mẫu dữ liệu nhỏ hoặc khi các thuộc tính có
phân phối không đồng đều giữa các lớp.
2.5 THUẬT TOÁN SUPPORT VECTOR MACHINE (SVM) Thuật toán
Support Vector Machine (SVM) là một thuật toán học có giám

12. sát được sử dụng để phân loại hoặc dự đoán giá trị của một biến mục tiêu dựa
trên các thuộc tính đầu vào. Nó tìm ra một siêu phẳng tốt nhất để phân chia các
lớp dữ liệu.
2.5.1 Xây dựng SVM


Chọn hai lớp dữ liệu cần phân loại.


Tìm một siêu phẳng tốt nhất để phân chia hai lớp dữ liệu. Siêu phẳng này
được chọn sao cho khoảng cách từ siêu phẳng đến điểm gần nhất của mỗi lớp là
lớn nhất.


Để xử lý các trường hợp không thể phân chia bằng một siêu phẳng, ta có thể
sử dụng kernel SVM để ánh xạ dữ liệu vào một không gian cao hơn, nơi các lớp
có thể được phân chia bằng một siêu phẳng.


Tìm các vector hỗ trợ (support vectors), tức là các điểm dữ liệu gần nhất với
siêu phẳng. Các vector hỗ trợ này được sử dụng để tính toán khoảng cách từ
siêu phẳng đến các điểm dữ liệu mới.
2.5.2 Phân loại mẫu dữ liệu mới
Khi siêu phẳng đã được xác định, ta có thể sử dụng nó để phân loại mẫu dữ liệu
mới bằng cách tính toán khoảng cách từ mẫu dữ liệu đó đến siêu phẳng. Nếu
khoảng cách này nhỏ hơn một ngưỡng được xác định trước, mẫu dữ liệu sẽ
được phân loại vào lớp tương ứng với phía của siêu phẳng mà nó nằm.
2.5.3 Ưu điểm của SVM
Ưu điểm


Tính linh hoạt: SVM có thể sử dụng nhiều kernel khác nhau để ánh xạ dữ liệu
vào không gian cao hơn, giúp phân loại chính xác hơn.


Tính ổn định: SVM có khả năng giảm thiểu overfitting và underfitting, tức là
mô hình không chỉ tốt trên tập huấn luyện mà còn tốt trên tập kiểm tra.

Hiệu
suất cao: SVM có hiệu suất cao trong việc phân loại dữ liệu nhiều chiều.
CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN KNN CHO
BÀI TOÁN PHÂN LOẠI SẢN PHẨM

13. 3.1 PHÂN TÍCH THUẬT TOÁN KNN (K-NEAREST NEIGHBORS)
3.1.1 Lý do chọn thuật toán
Nhóm em chọn thuật toán KNN vì nó là một thuật toán đơn giản, hiệu quả và có
độ chính xác cao trong việc phân loại và dự đoán. Nó cũng không yêu cầu giả
định về phân phối của dữ liệu và dễ dàng triển khai. KNN không đòi hỏi thời
gian huấn luyện lớn như các thuật toán khác. Việc huấn luyện mô hình chỉ đơn
giản là lưu trữ dữ liệu huấn luyện và có thể dễ dàng mở rộng
3.1.2 Quy trình làm việc của thuật toán KNN
Quy trình cơ bản của thuật toán K-Nearest Neighbors (KNN) trong bài toán
phân loại có các bước như sau:
1. Xác định tham số K: Chọn giá trị K phù hợp là một quá trình quan trọng
trong thuật toán KNN. Giá trị K quyết định số lượng láng giềng sẽ được sử
dụng để dự đoán lớp của điểm dữ liệu mới.
2. Tính khoảng cách: Tính khoảng cách giữa điểm dữ liệu mới và các điểm dữ
liệu trong tập huấn luyện. Thuật toán KNN có thể sử dụng khoảng cách Euclid
hoặc khoảng cách Manhattan để tính khoảng cách.
3. Sắp xếp khoảng cách: Sắp xếp khoảng cách từ điểm dữ liệu mới tới các điểm
dữ liệu huấn luyện theo thứ tự tăng dần.
4. Chọn K láng giềng gần nhất: Lấy K điểm gần nhất với điểm dữ liệu mới dựa
trên khoảng cách tính toán.
5. Dự đoán lớp của điểm mới: Dựa trên số lượng láng giềng thuộc mỗi lớp,
thuật toán KNN dự đoán lớp của điểm dữ liệu mới. Các láng giềng thuộc cùng
một lớp sẽ được tính là một phiếu bầu cho lớp đó, và lớp có số phiếu bầu cao
nhất sẽ được chọn là lớp dự đoán cho điểm dữ liệu mới.
3.1.3. Ví dụ minh họa
Ví dụ về phân loại KNN:

14. Hình 2 : Ví dụ về thuật toán KNN
Mẫu thử nghiệm (chấm màu xanh lá cây) nên được phân loại
thành hình vuông màu xanh lam hoặc hình tam giác màu đỏ.
Nếu k = 3 (vòng tròn đường liền khối) nó được gán cho các tam
giác màu đỏ vì có 2 hình tam giác và chỉ có 1 hình vuông bên trong
vòng tròn bên trong. Nếu k = 5 (vòng tròn đường đứt nét), nó được gán
cho các hình vuông màu xanh lam (3 hình vuông so với 2 hình tam giác
bên trong vòng tròn bên ngoài).
3.1.4. Ví dụ về KNN nhiễu
Hình 3 : Bản đồ minh họa KNN nhiễu với K=1
Hình trên là bài toán phân lớp với ba lớp: đỏ, lam, lục. Mỗi điểm dữ liệu mới sẽ
được gán nhãn theo màu của điểm đó mà nó thuộc về. Trong hình này, chú ý
vùng khoanh tròn màu vàng, ta nhận thấy rằng điểm màu lục nằm giữa hai vùng

15. lớn với nhiều dữ liệu đỏ và lam, điểm này rất có thể là nhiễu dẫn đến việc dữ
liệu test nếu rơi vào vùng này sẽ có nhiều khả năng cho kết quả sai lệch.
3.1.5 Phân tích toán học
Không có hàm mất mát hay bài toán tối ưu nào cần thực hiện trong quá trình
huấn luyện KNN. Mọi tính toán được tiến hành ở bước kiểm tra. Vì KNN ra
quyết định dựa trên các điểm gần nhất nên có hai vấn đề ta cần lưu tâm. Thứ
nhất, khoảng cách được định nghĩa như thế nào. Thứ hai, cần phải tính toán
khoảng cách như thế nào cho hiệu quả.
Với vấn đề thứ nhất, mỗi điểm dữ liệu được thể hiện bằng một vector đặc trưng.
khoảng cách giữa hai điểm chính là khoảng cách giữa hai vector đó. Có nhiều
loại khoảng cách khác nhau tùy vào bài toán, nhưng khoảng cách được sử dụng
nhiều nhất là khoảng cách Euclid.
Vấn đề thứ hai cần được lưu tâm hơn, đặc biệt với các bài toán có tập huấn
luyện lớn và vector dữ liệu có kích thước lớn. Giả sử các vector huấn luyện là
các cột của ma trận X
∈
RdxN với d và N lớn. KNN sẽ phải tính khoảng cách
từ một điểm dữ liệu mới z
∈
Rd đến toàn bộ N điểm dữ liệu đã cho và chọn ra
K khoảng cách nhỏ nhất. Nếu không có cách tính hiệu quả, khối lượng tính toán
sẽ rất lớn.
Tiếp theo, chúng ta cùng thực hiện một vài phân tích toán học để tính các
khoảng cách một cách hiệu quả. Ở đây khoảng cách được xem xét là khoảng
cách Euclid.
3.1.5.1 Khoảng cách từ một điểm tới từng điểm trong một tập hợp Khoảng
cách Euclid từ một điểm z tới một điểm xi trung tập huấn luyện được định nghĩa
bởi || z-xi ||2. Người ta thường dùng bình phương khoảng cách Euchid || z-xi ||
2
2 để
tránh phép tính căn bậc hai. Việc bình phương này không ảnh hưởng tới thứ tự
của các khoảng cách. Để ý rằng
||z-x i ||
2
2 = (z – xi)
T
(z – xi ) =||z||
2
2 +||x i ||
2
2 -2x
T
iz (1)
Để tìm ra xi gần với z nhất, số hạng đầu tiên có thể được bỏ qua. Hơn nữa, nếu
có nhiều điểm dữ liệu trong tập kiểm tra, các giá trị ||xi||
2
2 có thể được tính và lưu
trước vào bộ nhớ. Khi đó, ta chỉ cần tính các tích vô hướng 2x
T
iz.
Để thấy rõ hơn, chúng ta cùng là một ví dụ trên Python. Trước hết, chọn d và N
là các giá trị lớn và khai báo ngẫu nhiên X và z. Khi lập trình Python, cần lưu ý
rằng chiều thứ nhất thường chỉ thứ tự của điểm dữ liệu.
from _future_ import print _function
import numpy as np

16. from time import time # comparing runing time
d, N =1000, 10000 # dimension, number of training points
X = np.random.randn (N, d) # N d-dimensional points
z= np.random.randn(d)
Tiếp theo, ta viết ba hàm số:
a. dist_pp(z, x) tính bình phương khoảng cách Euclid giữa z và x. Hàm này tính
hiệu z − x rồi lấy bình phương l2 norm của nó. b. dist_ps_naive(z, X) tính bình
phương khoảng cách giữa 2 và mỗi hàng của x. Trong hàm này, các khoảng
cách được xây dựng dựa trên việc tính từng giá trị dist_pp(z, X[i]).
c. dish_ps_fast(z, X) tính bình phương khoảng cách giữa 2 và mỗi hàng của X.
tuy nhiên, kết quả được tính dựa trên đẳng thức (1). Tà cần tỉnh tổng bình
phương các phần tử của mối điểm dữ liệu trong X và tính tích X.dot(z).
Đoạn code dưới đây thể hiện hai cách tính khoảng cách từ một điểm 2 tới một
tập hợp điểm X. Kết quả và thời gian chạy của mỗi hàm được in ra để so sánh.
def dist_pp(z, x):
d = z – x.reshape(z. shape)
return np.sum (d*d)
def dist_ps_naive (z, X): N = X.shape[0]
res = np.zeros((1, N))
for i in range (N):
res[0][1] = dist_pp (z, X[i])
return res
def dist_ps_fast (z, X):
X2 = np. sum (X*X, 1)
z2 = np. sum (z*z)
return X2 + z2 - 2*x.dot (z)

17. t1 = time ()
D1 = dist_ps_naive (z, X)
print('naive point 2set, running time:', time () - t1, 's')
t1= time ()
D2 = dist_ps_fast (z, X)
print (‘fast point2set, running time:', time () – t1, 's')
print (‘Result difference:', np. linalg.norm (D1- D2))
Kết quả
naive point2set, running time: 0.093254804612 s
fast point 2set running time: 0.05h178276062 s
Result difference: 2.h81965531e-1
Kết quả chỉ ra rằng hàm dist_ps_fast(z, X) chạy nhanh hơn gần
gấp đối so với hàm dist_ps_naive (z, X). Tỉ lệ này còn lớn hơn khi kích
thước dữ liệu tăng lên và X2 được tính từ trước. Quan trọng hơn, sự
chênh lệch nhỏ giữa kết quả của hai cách tính chỉ ra rằng dist_ps_fast(z,
X) nên được ưu tiên hơn.
3.1.5.2 Khoảng cách giữa từng cặp điểm trong hai tập hợp
Thông thường, tập kiểm tra bao gồm nhiều điểm dữ liệu tạo thành ma trận Z. Ta
phải tính từng cặp khoảng cách giữa mỗi điểm trong tập kiểm tra và một điểm
trong tập huấn luyện. Nếu mỗi tập có 1000 phần tử, có một triệu khoảng cách
cần tính. Nếu không có phương pháp tính hiệu quả, thời gian thực hiện sẽ rất
dài.
Đoạn code dưới đây thể hiện hai phương pháp tính bình phương khoảng cách
giữa các cặp điểm trong hai tập điểm. Phương pháp thứ nhất sử dụng một vòng
for tính khoảng cách từ từng điểm trong tập thứ đến tất cả các điểm trong tập

18. thứ hai thông qua hàm dist_ps_fast (z, X) ở trên. Phương pháp thứ hai tiếp tục
sử dụng (1) cho trường hợp tổng quát.
Z = np.random.randn (100, d)
def dist_ss_0 (Z, X):
M, N = Z.shape[0], X.shape[0]
Res = np.zeros((M, N)
for i in range (M):
res(1) = dist_ps_fast (Z[i],X)
return res
def dist_ss_fast (Z, X) :
X2 = np.sum(X*X,1)
Z2 = np.sum (Z*Z, 1)
return Z2. reshape (-1, 1) + X2.reshape (1, - 1) – 2Z.dot (X, T) t1 = time()
D3 = dist_ss_0 (Z, X)
print('half fast set2set running time:', time () - t1 ,’ s’)
t1 = time ()
D4 = dist_ss_fast (Z, X)
print('fast set 2set running time', time () – t1, 's')
print('Result difference:', np.linalg.norm (D3 - D4))
Kết quả
half fast set 2set running time: 4.33642292023

19. fast set2set running time 0.05832505226h s
Result difference: 9.93586539607e-1
Điều này chỉ ra rằng hai cách tính cho kết quả chênh lệch nhau
không đáng kể. Trong khi đó dist_ss_fast(Z, X) chạy nhanh hơn
dist_ss_0(Z, X) nhiều lần.
3.2 CÁC THƯ VIỆN CHÍNH ĐƯỢC SỬ DỤNG
a. Thư viện Numpy
Numpy là một thư viện Python được sử dụng rộng rãi trong các
tác vụ tính toán khoa học và toán học. Nó cung cấp cho người dùng
một loạt các công cụ để làm việc với mảng đa chiều (array) và ma trận,
cũng như các hàm toán học để thực hiện các phép tính số học trên các
mảng này. Các tính năng chính của Numpy bao gồm: mảng đa chiều
(array), các phép tính toán số học, truy cập và thay đổi phần tử của
mảng. Numpy còn có thể tích hợp tốt với các thư viện khác như
Pandas, Matplotlib và Scikit-learn.
b. Thư viện Scikit-learn
Scikit-learn là một thư viện Python phổ biến được sử dụng trong
các tác vụ học máy và khai phá dữ liệu. Nó cung cấp cho người dùng
một loạt các công cụ để thực hiện các tác vụ như phân loại, hồi quy,
phân cụm và giảm chiều dữ liệu. Với các tính năng mạnh mẽ của mình,
Scikit-learn là một trong những thư viện học máy phổ biến nhất và
được sử dụng rộng rãi trong cộng đồng học máy và khoa học dữ liệu.
3.3 BỘ DỮ LIỆU WINE
Bộ dữ liệu được lấy từ trang
https://archive.ics.uci.edu/dataset/109/wine. Đây là một bộ dữ liệu về
phân loại rượu, nó có chứa thông tin các chỉ số hóa học của 178 mẫu và
13 thuộc tính, được chia thành 3 loại khác nhau có giá trị là [1], [2], [3]
theo cột dữ liệu Wine. Các thuộc tính là:

20. 1. Alcohol
2. Malic acid
3. Ash
4. Alcalinity of ash
5. Magnesium
6. Total phenol intake
7. Flavanoids
8. Nonflavanoid phenols 9. Proanthocyanins
10.Color Intensity
1.Hue
12.OD280/OD315 of diluted wine
13.Proline
3.4 CÀI ĐẶT MÔI TRƯỜNG
Cài đặt Pycharm IDE
Bước 1: Truy cập vào website của JetBrains:
https://www.jetbrains.com/pycharm/
Bước 2: Nhấn chọn “Download”
Hình 4 : Giao diện trang chủ của PyCharm tại JetBrains

21. Bước 3: Tại đây, bạn sẽ thấy 2 phiên bản PyCharm:


Bản Professional: Chứa đầy đủ các tính năng từ cơ bản đến nâng cao để lập
trình Python. Tuy nhiên, phiên bản này bạn sẽ phải mua bản quyền để sử dụng.


Bản Community: Chỉ chứa những tính năng cơ bản để lập trình Python. Tuy
nhiên, phiên bản này hoàn toàn miễn phí, bạn không cần trả phí như bản
Professional.
Hình 5 : Tùy vào nhu cầu của bạn, hãy lựa chọn tải về phiên bản phù hợp
Bước 4: Sau khi tải xuống thành công, PyCharm sẽ được lưu tại thư mục
Download của máy tính. Lúc này, bạn nhấn đúp chuột vào thư mục để bắt đầu
cài đặt PyCharm.
Giao diện chào mừng như sau được hiển thị, chọn Next để tiếp tục cài đặt.

22. Hình 6 : Màn hình chào mừng của PyCharm
Bước 5: Cửa sổ thiết lập vị trí cài đặt sẽ xuất hiện, bạn có thể chọn một thư mục
cho vị trí cài đặt hoặc giữ lại đường dẫn mặc định. Sau đó, tiếp tục chọn Next để
đến bước tiếp theo.
Hình 7 : Lựa chọn thư mục chứa PyCharm
Bước 6: Tiếp theo, bạn sẽ tiến hành lựa chọn các tùy chọn cho việc cài đặt. Nếu
máy tính của bạn chưa cài đặt Java thì hãy tích vào tất cả các tùy chọn trên màn
hình này.

23. Hình 8 : Hướng dẫn một số cài đặt PyCharm
Bước 7: Chọn Install để thực hiện quá trình cài đặt. Sau khi cài đặt xong thì
nhấn Finish để hoàn tất quá trình.
Hình 9 : Chọn Install để bắt đầu cài đặt
3.5 THỰC HIỆN XÂY DỰNG MÔ HÌNH


Môi trường thực hiện: Pycharm


Các bước xây dựng mô hình cho bài toán.
- Chuẩn bị dữ liệu: Tải dữ liệu về và lưu trữ dữ liệu vào trong pycharm - Tiền
xử lý dữ liệu: Chuẩn hóa dữ liệu

24. - Xây dựng mô hình KNN: Áp dụng thuật toán KNN để phân loại dữ liệu -
Đánh giá mô hình: Đánh giá mô hình bằng cách đưa tập kiểm tra qua mô hình
và tính toán độ chính xác của mô hình.
a) Chuẩn bị dữ liệu
import numpy as np
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
# Đọc dữ liệu từ tập tin
data = np.genfromtxt('wine.data', delimiter=',')
b) Tiền xử lý dữ liệu
# Tách features (X) và labels (y)
X = data[:, 1:] # Lấy các cột từ 1 đến cuối
y = data[:, 0] # Lấy cột đầu tiên
# Chia dữ liệu thành tập huấn luyện và tập kiểm tra
X_train, X_test, y_train, y_test = train_test_split(X, y,
test_size=0.2, random_state=42)
c) Xây dựng mô hình KNN
# Xây dựng mô hình KNN
knn = KNeighborsClassifier(n_neighbors=3)
# Huấn luyện mô hình

25. knn.fit(X_train, y_train)
d) Đánh giá mô hình
# Dự đoán nhãn cho tập kiểm tra
y_pred = knn.predict(X_test)
# In ra các nhãn dự đoán
print("Các nhãn dự đoán: ", y_pred)
# In ra các nhãn thực tế
print("Các nhãn thực tế: ", y_test)
# So sánh các nhãn dự đoán với các nhãn thực tế
for i in range(len(y_pred)):
if y_pred[i] == y_test[i]:
print("Mẫu ", i, "được phân loại chính xác")
else:
print("Mẫu ", i, "được phân loại sai, nhãn dự đoán là", y_pred[i], ",
nhãn thực tế là", y_test[i])
# Đánh giá độ chính xác của mô hình
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)
3.6 KẾT QUẢ ĐẠT ĐƯỢC

26. Các nhãn dự đoán: [3. 1. 3. 1. 2. 1. 2. 3. 1. 1. 3. 3. 1. 2. 1. 2. 2. 2. 1. 2. 1. 2. 3. 3.
2. 3. 2. 3. 2. 1. 1. 2. 3. 1. 1. 1.]
Các nhãn thực tế: [1. 1. 3. 1. 2. 1. 2. 3. 2. 3. 1. 3. 1. 2. 1. 2. 2. 2. 1. 2. 1. 2. 2. 3.
3. 3. 2. 2. 2. 1. 1. 2. 3. 1. 1. 1.]
Mẫu 0 được phân loại sai, nhãn dự đoán là 3.0 , nhãn thực tế là 1.0 Mẫu 1 được
phân loại chính xác
Mẫu 2 được phân loại chính xác
Mẫu 3 được phân loại chính xác
Mẫu 4 được phân loại chính xác
Mẫu 5 được phân loại chính xác
Mẫu 6 được phân loại chính xác
Mẫu 7 được phân loại chính xác
Mẫu 8 được phân loại sai, nhãn dự đoán là 1.0 , nhãn thực tế là 2.0 Mẫu 9 được
phân loại sai, nhãn dự đoán là 1.0 , nhãn thực tế là 3.0 Mẫu 10 được phân loại
sai, nhãn dự đoán là 3.0 , nhãn thực tế là 1.0 Mẫu 1 được phân loại chính xác
Mẫu 12 được phân loại chính xác
Mẫu 13 được phân loại chính xác
Mẫu h được phân loại chính xác
Mẫu 15 được phân loại chính xác
Mẫu 16 được phân loại chính xác
Mẫu 17 được phân loại chính xác Mẫu 18 được phân loại chính xác Mẫu 19
được phân loại chính xác Mẫu 20 được phân loại chính xác Mẫu 21 được phân
loại chính xác
Mẫu 22 được phân loại sai, nhãn dự đoán là 3.0 , nhãn
thực tế là 2.0 Mẫu 23 được phân loại chính xác
Mẫu 24 được phân loại sai, nhãn dự đoán là 2.0 , nhãn
thực tế là 3.0 Mẫu 25 được phân loại chính xác
Mẫu 26 được phân loại chính xác
Mẫu 27 được phân loại sai, nhãn dự đoán là 3.0 , nhãn
thực tế là 2.0 Mẫu 28 được phân loại chính xác

27. Mẫu 29 được phân loại chính xác
Mẫu 30 được phân loại chính xác
Mẫu 31 được phân loại chính xác
Mẫu 32 được phân loại chính xác
Mẫu 33 được phân loại chính xác
Mẫu 34 được phân loại chính xác
Mẫu 35 được phân loại chính xác
Accuracy: 0.8055555555555556
KẾT LUẬN
Trong quá trình thực hiện bài tập lớn này, nhóm em bắt đầu với việc tìm hiểu cơ
bản về thuật toán KNN và cách nó hoạt động. Sau đó nhóm em sử dụng tập dữ
liệu đã được cho để huấn luyện mô hình KNN. Quá trình huấn luyện này bao
gồm việc chia dữ liệu thành tập huấn luyện và tập kiểm tra, xác định số lượng
láng giềng gần nhất (K), tính toán khoảng cách giữa các điểm dữ liệu và xác
định lớp phân loại dựa trên đa số láng giềng gần nhất. Sau khi thực hiện quá
trình trên thì em đã có thể nắm được thuật toán KNN, cách xây dựng mô hình
và đánh giá hiệu suất. Bên cạnh đó nhóm em vẫn còn một số việc chưa làm
được như là tìm hiểu thêm những thuật toán có thể áp dụng cho bài toán phân
loại sản phẩm và so sánh. Vì vậy sau khi thực hiện bài tập lớn, nhóm em sẽ
khám phá các thuật toán khác có thể áp dụng vào bài toán phân loại sản phẩm
để từ đó có thể lựa chọn được thuật toán cho phù hợp với các đề bài phân loại
khác nhau. Tóm lại, sau khi thực hiện bài tập lớn tìm hiểu và ứng dụng thuật
toán KNN để phân loại sản phẩm, em đã có những thành quả và công việc hoàn
thành. Tuy nhiên,nhóm em cũng nhận thấy rằng còn nhiều điều để học và cải
thiện. Nhóm em sẽ tiếp tục khám phá và phát triển kiến thức của mình trong
lĩnh vực machine learning và phân loại dữ liệu.