Thuật toán Machine Learning mà lập trình viên nên biết

Thuật toán là nền tảng kiến thức cần thiết với bất kì lập trình viên nào. Dưới dây, tôi sẽ giới thiệu 10 thuật toán Machine Learning phổ biến nhất mà mỗi lập trình viên cần biết.

Đây sẽ là hướng dẫn cho những bạn bắt đầu theo học Machine Learning.

Hi vọng bài viết giúp ích cho các bạn.

1. Cây quyết định (Decision Trees)

Đây là một trong những thuật toán phổ biến nhất được sử dụng hiện nay. Cây quyết định là thuật toán học có giám sát, dùng để phân loại các vấn đề. Thuật toán có thể thực hiện cho cả biến phân loại và biến liên tục. Trong thuật toán này, ta chia dữ liệu thành 2 hoặc nhiều lớp dựa trên phân loại theo các thuộc tính/biến quan trọng.

Đứng dưới góc nhìn thực tế, cây quyết định là một danh sách tối thiểu các câu hỏi dạng yes/no mà người ta phải hỏi, để đánh giá xác suất đưa ra quyết định đúng đắn.

Dưới đây là mô hình ví dụ về cây quyết định:

Cây quyết định

Nhìn từ cây quyết định trên, ta có thể rút ra được kết luận: Nếu trời nắng & độ ẩm trung bình thì người chơi sẽ quyết định “Yes”.

Tuy nhiên, ta cần chú ý tới vấn đề Overfitting trong thuật toán này. Để giảm hiện tượng này, ta thường dùng phương pháp cắt tỉa cây.

2. Phân loại Bayes

Thuật toán phân loại Naive Bayes là một nhóm các phân loại xác suất đơn giản dựa trên định lý Bayes giả định về việc độc lập giữa các thuộc tính.

Ngay cả khi, các thuộc tính này có sự tương quan với nhau thì phương pháp này vẫn xem các thuộc tính là độc lập với nhau.

Trong đó: P(A|B) là xác suất có điều kiện A khi biết B, P(A) là xác suất giả thuyết A (tri thức có được về giải thuyết A trước khi có dữ liệu B), P(B|A) là xác suất có điều kiện B khi biết giả thuyết A,P(B) là xác suất của dữ liệu quan sát B không quan tâm đến bất kỳ giả thuyết A nào.

Thuật toán này được áp dụng trong một số bài toán như:

  • Đánh dấu một email là spam hay không.
  • Phân loại bài viết tin tức thuộc lĩnh vực công nghệ, chính trị hay thể thao.
  • Kiểm tra một đoạn văn bản mang cảm xúc tích cực hay tiêu cực.
  • Sử dụng cho các phần mềm nhận diện khuôn mặt. …

Ưu điểm của thuật toán này là sự đơn giản, ta có thể dễ dàng xây dựng và áp dụng được với bộ dữ liệu lớn. Phương pháp này thể hiện kết quả hữu ích hơn rất nhiều phương pháp tinh vi khác.

3. Hồi quy tuyến tính

Bạn có thể tưởng tượng bằng cách sắp xếp các khúc gỗ ngẫu nhiên theo thứ tự tăng dần của trọng lượng khúc gỗ. Tuy nhiên, sẽ có một vấn đề ở đây là ta không thể cân các khúc gỗ lên được. Bạn sẽ đoán trọng lượng của chúng thông qua trực quan theo chiều cao và đường kính của chúng rồi sắp xếp chúng. Đó là những gì thuật toán này thực hiện.

Trong thuật toán này, sẽ có một hàm thể hiện mối quan hệ giữa các biến độc lập và biến phụ thuộc. Đây được gọi là phương trình hồi quy được biểu diễ bằng phương trình tuyến tính cơ bản:

Y= a *X + b

Trong đó:

  • Y : biến phụ thuộc
  • a : hệ số dốc
  • X: biến độc lập
  • b: hệ số chặn
Đường hồi quy tuyến tính

Trong thuật toán này, có rất nhiều hướng để ta sắp xếp khúc gỗ trên. Hay nói cách khác là ta tìm một đường thẳng đi một tập các điểm. Phương pháp “bình phương nhỏ nhất” cũng là một phương pháp chính trong thuật toán này. Phương pháp này sẽ đo khoảng các từ đường thẳng mới được tạo tới tất cả các điểm trong tập dữ liệu. Đường phù hợp nhất sẽ là đường mà các khoảng cách này càng nhỏ càng tốt. 

4. Hồi quy Logistic

Hồi quy Logistic được dùng để ước tính các giá trị rời rạc (thường là những giá trị nhị phân như 0/1) từ một tập hợp các biến rời rạc. Mô hình giúp dự đoán xác suất xảy ra của một sự kiện thông qua hàm logit.

Một số phương pháp thường được sử dụng để cải thiện mô hình Logistic như:

  • Sử dụng mô hình phi tuyến
  • Chuẩn hóa lại các thông số kỹ thuật
  • Loại bỏ những biến không cần thiết
  • Xác định các mối liên hệ

Thuật toán này được sử dụng trong một số trường hợp:

  • Điểm tín dụng ( quyết định có cho khách hàng vay vốn hay không)
  • Đo mức độ thành công của chiến dịch marketing
  • Dự đoán doanh thu của một sản phẩm nhất định
  • Dự đoán động đất ….

5. Support Vector Machine – SVM

SVM là phương pháp phân loại trong đó dữ liệu thô của bạn sẽ được biểu diễn trên không gian n chiều (n-số thuộc tính). Thông qua không gì biểu diễn diễn dự liệu đó, ta có thể thực hiện phân loại dữ liệu.

Ví dụ, cho một tập các điểm thuộc 2 loại trong môi trường N chiều, SVM cố gắng tìm ra N-1 mặt phẳng để phân tách các điểm đó thành 2 nhóm. Ví dụ, cho một tập các điểm thuộc 2 loại như hình bên dưới, SVM sẽ tìm ra một đường thẳng nhằm phân cách các điểm đó thành 2 nhóm sao cho khoảng cách giữa đường thẳng và các điểm xa nhất có thể.

SVM thực hiện giải quyết rất nhiều dạng bài toán như hiển thị quảng cáo, phát hiện giới tính dựa trên hình ảnh, phân loại hình ảnh có quy mô lớn …

6. K-nearest neighbors

Thuật toán này được áp dụng cho cả bài toán phân loại và hồi quy. Trên thực tế, thuật toán này thường được sử dụng giải quyết các bài toán phân loại hơn. Một dữ liệu mới sẽ được biểu diễn trên không gian, so sánh với những dữ liệu gần nó và phân loại nó theo nhiều điểm chung nhất.Ta sẽ có một hàm thực hiện đo khoảng cách này.

KNN là thuật toán dựa theo đời sống thực. Ví dụ, bạn muốn hiểu được một người thì có một cách là bạn có thể thông qua những người xung quanh người đó.

Phân loại KNN

Một số lưu ý với thuật toán KNN:

  • Chi phí thực hiện KNN là khá đắt
  • Dữ liệu cần được chuẩn hóa trước vì những biến có giá trị cao sẽ làm nhiễu mô hình thuật toán
  • Dữ liệu cần được xử lý trước

7. K-mean

Đây là thuật toán không giám sát để xử lý các bài toán phân cụm. Tập dữ liệu sẽ được phân loại thành các cụm cụ thể trên không gian biểu diễn (gọi là k cụm) sao cho tất cả các dữ liệu trong cụm là giống nhau và khác với những cụm khác ở những đặc điểm chính.

Gom cụm có nhiều phương pháp khác nhau, sau đây là một vài trong số đó:

  • Gom cụm dựa vào tâm điểm (Centroid-based algorithms)
  • Gom cụm dựa vào tính kết nối (Connectivity-based algorithms)
  • Gom cụm dựa vào mật độ (Density-based algorithms)
  • Gom cụm dựa vào xác suất (Probabilistic)
  • Gom cụm dựa trên giảm chiều dữ liệu (Dimensionality Reduction)
  • Gom cụm dựa trên mạng nơ-ron/deep leanring (Neural networks / Deep Learning)

8. Random Forest

Một tập hợp các cây quyết định được gọi là Random Forest. Để phân loại một đối tượng mới dựa trên các thuộc tính của nó, mỗi cây được phân loại và cây Bầu chọn phiếu bầu cho lớp đó. Rừng chọn phân loại có nhiều phiếu nhất (trên tất cả các cây quyết định).

Mỗi cây được xây dựng & biểu diễn như sau:

  • Nếu số lượng các trường hợp trong tập huấn luyện là N, thì một mẫu các trường hợp N được lấy ngẫu nhiên. Mẫu này sẽ là tập huấn luyện để trồng cây.
  • Nếu có các biến đầu vào M, một số m << M được chỉ định sao cho tại mỗi nút, m biến được chọn ngẫu nhiên ngoài M và phân chia tốt nhất trên các m này được sử dụng để phân chia nút. Giá trị của m được giữ không đổi trong quá trình này.
  • Mỗi cây được xây dựng ở mức độ lớn nhất có thể. Và không có cắt tỉa.

9. PCA và SVD ( Dimensionality Reduction Algorithms – phương pháp giảm số chiều thuộc tính)

PCA là một thuật toán thống kê sử dụng phép biến đổi trực giao để biến đổi một tập hợp dữ liệu từ một không gian nhiều chiều sang một không gian mới ít chiều hơn (2 hoặc 3 chiều) nhằm tối ưu hóa việc thể hiện sự biến thiên của dữ liệu.

Phép biến đổi tạo ra những ưu điểm sau đối với dữ liệu:

  • Giảm số chiều của không gian chứa dữ liệu khi nó có số chiều lớn, không thể thể hiện trong không gian 2 hay 3 chiều.
  • Xây dựng những trục tọa độ mới, thay vì giữ lại các trục của không gian cũ, nhưng lại có khả năng biểu diễn dữ liệu tốt tương đương, và đảm bảo độ biến thiên của dữ liệu trên mỗi chiều mới.
  • Tạo điều kiện để các liên kết tiềm ẩn của dữ liệu có thể được khám phá trong không gian mới, mà nếu đặt trong không gian cũ thì khó phát hiện vì những liên kết này không thể hiện rõ.
  • Đảm bảo các trục tọa độ trong không gian mới luôn trực giao đôi một với nhau, mặc dù trong không gian ban đầu các trục có thể không trực giao. 

Một số ứng dụng của PCA bao gồm nén, đơn giản hóa dữ liệu để dễ dàng học tập, hình dung. Lưu ý rằng kiến thức miền là rất quan trọng trong khi lựa chọn có nên tiếp tục với PCA hay không. Nó không phù hợp trong trường hợp dữ liệu bị nhiễu (tất cả các thành phàn của PCA đều có độ biến thiên khá cao)

Trong đại số tuyến tính, SVD là một thừa số của ma trận phức tạp thực sự. Đối với một ma trận m*n đã xác định M, tồn tại một sự phân rã sao cho M = UΣV, trong đó U và V là các ma trận đơn nhất và Σ là một ma trận chéo.

PCA thực ra là một ứng dụng đơn giản của SVD. Trong khoa học máy tính, các thuật toán nhận dạng khuôn mặt đầu tiên được sử dụng PCA và SVD để biểu diễn khuôn mặt như là một sự kết hợp tuyến tính của “eigenfaces”, làm giảm kích thước, và sau đó kết hợp khuôn mặt với các tính chất thông qua các phương pháp đơn giản. Mặc dù các phương pháp hiện đại phức tạp hơn nhiều, nhiều người vẫn còn phụ thuộc vào các kỹ thuật tương tự.

10. Gradient Boosting & AdaBoost

Boosting là một kĩ thuật đồng bộ nhằm cố gắng tạo ra một phương pháp phân loại mạnh từ một số phương pháp phân loại yếu. Điều này được thực hiện bằng cách xây dựng mô hình từ dữ liệu đào tạo, sau đó tạo ra một mô hình thứ hai cố gắng sửa lỗi từ mô hình đầu tiên. Các mô hình được thêm vào cho đến khi tập đào tạo được dự đoán hoàn hảo hoặc thêm một số mô hình tối đa.

AdaBoost là thuật toán boosting thành công đầu tiên được phát triển để phân loại nhị phân. Đây là điểm khởi đầu tốt nhất để hiểu về boosting. Các phương pháp boosting hiện đại xây dựng trên AdaBoost, đáng chú ý nhất là các máy boosting gradient ngẫu nhiên.

AdaBoost được sử dụng với các decision trees ngắn. Sau khi cây đầu tiên được tạo ra, hiệu suất của cây trên mỗi trường hợp huấn luyện được sử dụng để đo độ chú ý của cây kế tiếp được tạo nên chú ý đến từng trường hợp đào tạo. Dữ liệu đào tạo khó dự đoán sẽ có trọng lượng hơn, trong khi những trường hợp dễ dự đoán có ít trọng lượng hơn. Các mô hình được tạo theo thứ tự tuần tự, mỗi lần cập nhật các trọng số trên các trường hợp đào tạo ảnh hưởng đến việc học được thực hiện bởi cây kế tiếp trong chuỗi. Sau khi tất cả các cây được xây dựng, dự đoán được thực hiện cho dữ liệu mới, và hiệu suất của mỗi cây được đo lường bằng cách nó đã được về dữ liệu đào tạo.

Bởi vì rất nhiều sự chú ý được đưa ra để sửa sai lầm theo thuật toán, điều quan trọng là bạn phải có dữ liệu sạch với các giá trị biên.

Đến đây là hết rồi. Bạn có thể tìm hiểu sâu hơn các thuật toán Machine Learning thông qua khóa học trên Coursera.

Hãy theo dõi https://trituenhantao.io/ để có nhiều kiến thức hơn nhé.

Bạn muốn trích dẫn bài này:
-----
"Thuật toán Machine Learning mà lập trình viên nên biết," Trí tuệ nhân tạo, Ngày xuất bản: 05/06/2019, URL: https://trituenhantao.io/kien-thuc/thuat-toan-machine-learning-ma-lap-trinh-vien-nen-biet/, Ngày truy cập: 11/07/2020.



Về trituenhantao.io

Trituenhantao.io là trang web chia sẻ thông tin, kiến thức, kinh nghiệm học tập và triển khai các chương trình và dự án sử dụng trí tuệ nhân tạo trên thế giới.
Xem tất cả các bài viết của trituenhantao.io →