Hiển thị các bài đăng có nhãn học máy. Hiển thị tất cả bài đăng
Hiển thị các bài đăng có nhãn học máy. Hiển thị tất cả bài đăng

Tổng quan về các phương pháp Học máy (Machine Learning) kinh điển và ứng dụng thực tiễn

Tổng quan về các phương pháp Học máy (Machine Learning) kinh điển và ứng dụng thực tiễn

Trong kỷ nguyên công nghệ 4.0, Trí tuệ nhân tạo (AI) và Khoa học dữ liệu (Data Science) đang thay đổi hoàn toàn cách chúng ta sống, làm việc và giải quyết vấn đề. Nằm ở vị trí trung tâm của cuộc cách mạng này chính là Machine Learning (Học máy). Khác với tư duy Lập trình (Programming) truyền thống - nơi con người phải tự tay viết ra từng quy tắc cứng nhắc (If-Else), Machine Learning trao cho máy tính khả năng tự động "học" các quy luật từ những luồng dữ liệu khổng lồ để đưa ra quyết định hoặc dự đoán một cách linh hoạt.


Ngày nay, khi nhắc đến AI, nhiều người thường nghĩ ngay đến các mạng nơ-ron nhân tạo sâu (Deep Learning) hay các mô hình ngôn ngữ lớn phức tạp. Tuy nhiên, trước khi đắm chìm vào những Framework đồ sộ đó, việc nắm vững các phương pháp học máy kinh điển là nền tảng vô giá. Chúng không chỉ nhanh, tốn ít tài nguyên tính toán mà còn có tính diễn giải cực kỳ cao. Bài viết này sẽ giúp bạn có cái nhìn tổng quan, hệ thống và dễ hiểu nhất về tên gọi, phân loại, nguyên lý hoạt động cũng như các ứng dụng thực tiễn của chúng trong đời sống.

1. Lớp bài toán Học có giám sát (Supervised Learning)

Học có giám sát giống như việc một cậu học sinh giải toán có sự hướng dẫn tận tình của giáo viên. Dữ liệu đầu vào (Input) đưa cho máy tính sẽ luôn đi kèm với đáp án chính xác (được gọi là Nhãn - Label). Thuật toán sẽ làm nhiệm vụ tìm ra hàm số toán học, hay "sợi dây" liên kết giữa dữ liệu và đáp án đó. Khi quá trình huấn luyện kết thúc, nó có thể tự tin dự đoán đáp án cho những dữ liệu mới mà nó chưa từng thấy bao giờ.

1.1. Hồi quy tuyến tính (Linear Regression)

Đây là thuật toán "vỡ lòng" nhưng cực kỳ mạnh mẽ mà bất kỳ ai bước chân vào Data Science cũng phải học. Linear Regression được thiết kế để dự đoán một giá trị liên tục (như giá tiền, nhiệt độ, độ dài, doanh số).

  • Nguyên lý chính: Thuật toán sẽ cố gắng vẽ ra một đường thẳng (hoặc một siêu phẳng nếu dữ liệu có nhiều chiều) đi xuyên qua tập hợp các điểm dữ liệu. Nó sẽ liên tục tự tinh chỉnh góc nghiêng và vị trí của đường thẳng sao cho tổng sai số (khoảng cách từ các điểm dữ liệu thực tế đến đường thẳng) là nhỏ nhất.
  • Ưu & Nhược điểm: Huấn luyện rất nhanh, dễ dàng giải thích cho sếp hoặc khách hàng (tính diễn giải cao). Tuy nhiên, nó bị hạn chế nếu dữ liệu có mối quan hệ phức tạp (phi tuyến tính) hoặc có quá nhiều điểm nhiễu (outliers).
  • Ứng dụng thực tiễn:
    • Dự đoán giá bất động sản dựa trên diện tích, vị trí và số phòng ngủ.
    • Dự báo doanh số bán hàng trong quý tới dựa trên ngân sách chạy quảng cáo.
Hồi quy tuyến tính (Linear Regression)


Hình 1.1: Trực quan hóa nguyên lý tìm "đường thẳng phù hợp nhất" trong thuật toán Linear Regression. (nguồn https://aicandy.vn/hoi-quy-tuyen-tinh-linear-regression-tim-hieu-chi-tiet)

1.2. Hồi quy Logistic (Logistic Regression)

Mặc dù mang từ "Regression" (Hồi quy) trong tên gọi, nhưng thuật toán này lại sinh ra để giải quyết bài toán Phân loại (Classification), đặc biệt là phân loại nhị phân (chỉ đưa ra kết quả gồm 2 trường hợp như: Có/Không, 1/0, Đúng/Sai).

  • Nguyên lý chính: Thuật toán này sử dụng một hàm toán học đặc biệt gọi là Hàm Sigmoid (có dạng hình chữ S). Hàm này đóng vai trò như một bộ lọc, ép tất cả các kết quả đầu ra rơi vào khoảng từ 0 đến 1. Giá trị nhận được đại diện cho xác suất xảy ra của sự kiện. Ví dụ: Nếu xác suất tính ra > 0.5, máy tính phân loại đối tượng vào nhóm 1; nếu < 0.5, đối tượng thuộc nhóm 0.
  • Ứng dụng thực tiễn:
    • Bộ lọc thư rác (Spam Filter): Xác định một email gửi đến là Spam (1) hay Thư thường (0).
    • Ngân hàng: Dự đoán xem một hồ sơ tín dụng có khả năng bị vỡ nợ hay không.
    • Y tế: Chẩn đoán khối u là lành tính hay ác tính.
Hình 1.2: Trực quan hóa hàm logistic. (nguồn https://vn.linkedin.com/pulse/understanding-logistic-regression-model-laymans-words-omkar-sutar?tl=vi)


1.3. Cây quyết định (Decision Tree) & Rừng ngẫu nhiên (Random Forest)

Nếu bạn muốn một thuật toán mô phỏng chính xác nhất cách tư duy logic của con người, thì đây chính là lựa chọn hoàn hảo.

  • Nguyên lý chính của Decision Tree: Nó hoạt động giống hệt trò chơi "20 câu hỏi". Mô hình sẽ liên tục đặt ra các câu hỏi dạng Có/Không ở mỗi nhánh (Ví dụ: Trời có mưa không? -> Khách hàng có thu nhập trên 20 triệu không?) để chia nhỏ bộ dữ liệu cho đến khi đưa ra được phán đoán cuối cùng. Nhược điểm lớn nhất của Cây quyết định là dễ bị Overfitting (Học vẹt - thuộc lòng dữ liệu cũ nhưng dự đoán sai bét trên dữ liệu mới).
  • Giải pháp Random Forest: Để khắc phục tình trạng học vẹt, thuật toán "Rừng ngẫu nhiên" được tạo ra. Nó xây dựng hàng trăm, hàng ngàn Cây quyết định khác nhau một cách ngẫu nhiên. Kết quả cuối cùng sẽ được quyết định dựa trên hình thức "bầu chọn theo số đông" của tất cả các cây trong rừng.
  • Ứng dụng thực tiễn:
    • Hệ thống gợi ý sản phẩm (Recommendation System) cơ bản trên các trang thương mại điện tử.
    • Hệ thống chấm điểm tín dụng (Credit Scoring).
Cây quyết định (Decision Tree) & Rừng ngẫu nhiên (Random Forest)


Hình 2.1: Logic chia nhánh rẽ ngôi của thuật toán Decision Tree. (nguồn https://aicandy.vn/thuat-toan-random-forest-giai-thich-chi-tiet-va-ung-dung/)

1.4. Máy vector hỗ trợ (Support Vector Machine - SVM)

SVM là một thuật toán hạng nặng, cực kỳ tinh vi và mạnh mẽ, chuyên trị những tập dữ liệu phức tạp, có ranh giới phân định mờ nhạt.

  • Nguyên lý chính: Hãy tưởng tượng bạn có những viên bi màu xanh và màu đỏ nằm trộn lẫn trên một mặt bàn. Nhiệm vụ của SVM là kẻ một đường thẳng (hoặc một siêu phẳng - Hyperplane) để tách biệt hai loại bi này. Tuy nhiên, SVM không kẻ bừa; nó sẽ tìm ra con đường phân chia sao cho lề (Margin) - tức là khoảng cách từ đường kẻ đó đến những viên bi gần nhất của cả 2 phe - là rộng rãi và an toàn nhất. Các điểm dữ liệu nằm sát ranh giới được gọi là các Support Vectors.
  • Ứng dụng thực tiễn:
    • Nhận diện ký tự quang học (OCR) - đọc chữ viết tay trên giấy tờ, bưu phẩm.
    • Phân loại văn bản và phân tích cảm xúc (Sentiment Analysis) trên mạng xã hội.
Hình 2.2: SVM (nguồn https://luanvanhay.org/lam-thue/svm-thuat-toan-ho-tro-may-vec-to-support-vector-machines/)



2. Lớp bài toán Học không giám sát (Unsupervised Learning)

Trái ngược hoàn toàn với người anh em của mình, Học không giám sát giải quyết các bộ dữ liệu không hề có nhãn (Unlabeled Data). Máy tính sẽ đóng vai trò như một thám tử: tự thân vận động, lặn lội vào trong một "đống" dữ liệu hỗn độn để tự động tìm ra các đặc điểm ẩn, những mẫu (patterns) hoặc cấu trúc lặp lại mà thậm chí con người cũng chưa nhận ra.

2.1. Phân cụm K-Means (K-Means Clustering)

K-Means là thuật toán nổi tiếng và phổ biến nhất thuộc nhánh Phân cụm (Clustering).

  • Nguyên lý chính: Giả sử bạn muốn chia dữ liệu thành K nhóm (ví dụ K=3). Thuật toán sẽ thả ngẫu nhiên 3 điểm trung tâm (Centroids) vào không gian dữ liệu. Sau đó, nó thu nạp những điểm dữ liệu nằm gần mỗi tâm nhất về thành một đội. Tâm của mỗi nhóm sẽ liên tục di chuyển và tính toán lại vị trí cho đến khi các nhóm trở nên thực sự phân biệt và ổn định.
  • Ứng dụng thực tiễn:
    • Marketing: Phân khúc khách hàng (Customer Segmentation). Gom nhóm các khách hàng có cùng thói quen mua sắm để chạy chiến dịch quảng cáo cá nhân hóa hiệu quả.
    • Gom cụm các bài báo, tin tức có cùng chủ đề lại với nhau một cách tự động.
Phân cụm K-Means (K-Means Clustering)


Hình 3: Trực quan hóa cách thuật toán K-Means phân cụm các điểm dữ liệu rời rạc. (nguồn https://machinelearningcoban.com/2017/01/01/kmeans/)

2.2. Phân tích thành phần chính (PCA - Principal Component Analysis)

Trong Khoa học dữ liệu có một khái niệm gọi là "Lời nguyền số chiều" (Curse of Dimensionality) - khi dữ liệu của bạn có quá nhiều cột, quá nhiều thuộc tính khiến máy tính mất quá nhiều thời gian để xử lý. PCA chính là vị cứu tinh của bài toán này.

  • Nguyên lý chính: PCA là kỹ thuật giảm chiều dữ liệu (Dimensionality Reduction). Thay vì ném đi các biến, thuật toán toán học này nén, kết hợp và biến đổi dữ liệu cũ thành các "thành phần chính" mới. Các thành phần này tuy ít về số lượng, nhưng lại giữ lại được tới 90-95% lượng thông tin quan trọng nhất (phương sai) của bộ dữ liệu gốc.
  • Ứng dụng thực tiễn:
    • Nén hình ảnh, video (giữ nguyên các chi tiết nhận diện chính nhưng giảm mạnh dung lượng).
    • Tiền xử lý dữ liệu: Giúp tăng tốc độ xử lý cho các mô hình Machine Learning khác.
    • Trực quan hóa (Visualization) các bộ dữ liệu đa chiều (VD: bộ gene sinh học 10.000 chiều) xuống bản đồ 2D hoặc 3D.

3. Lớp bài toán Học tăng cường (Reinforcement Learning)

Học tăng cường (Reinforcement Learning - RL) mang đậm hơi hướng của tâm lý học hành vi: Học qua quá trình Thử và Sai (Trial and Error). Không hề có dữ liệu nào được đưa sẵn cho máy tính. Thay vào đó, mô hình (được gọi là Agent) sẽ tự do tương tác bên trong một môi trường cụ thể (Environment).

  • Nguyên lý chính: Mỗi khi Agent đưa ra một hành động, môi trường sẽ phản hồi lại. Nếu hành động đó tốt và hướng đến mục tiêu, Agent nhận được Phần thưởng (Reward). Nếu hành động tệ, nó bị Trừ điểm (Penalty). Bằng cách thực hiện hàng triệu triệu phép thử khác nhau, thuật toán (tiêu biểu như Q-Learning) sẽ tự động tối ưu hóa một "cuốn bí kíp" để giúp Agent lấy được nhiều phần thưởng nhất.
  • Ứng dụng thực tiễn:
    • Trí tuệ nhân tạo đánh bại con người trong game: AlphaGo (Cờ vây), AI chơi Dota 2, Starcraft.
    • Robot công nghiệp tự động học cách đi đứng, gắp thả đồ vật.
    • Huấn luyện hệ thống kiểm soát xe tự lái (Autonomous Driving).

4. Code minh họa cơ bản với thư viện Scikit-Learn

Một trong những lý do khiến Machine Learning bùng nổ là nhờ hệ sinh thái mã nguồn mở. Với thư viện nổi tiếng như scikit-learn của Python, những thuật toán toán học phức tạp đã được gói gọn lại. Bạn có thể xây dựng mô hình Hồi quy tuyến tính chỉ với vài dòng code cực kỳ thanh lịch:

import numpy as np
from sklearn.linear_model import LinearRegression

# 1. Chuẩn bị dữ liệu mẫu: X (Diện tích nhà), y (Giá nhà tương ứng)
X = np.array([[30], [45], [50], [70], [85], [100]]) # Đơn vị: m2
y = np.array([1.2, 1.8, 2.0, 3.1, 3.5, 4.5])        # Đơn vị: Tỷ VNĐ

# 2. Khởi tạo thuật toán
model = LinearRegression()

# 3. Huấn luyện (Train) mô hình tìm ra quy luật
model.fit(X, y)

# 4. Dự đoán (Predict) thử giá tiền cho một căn nhà 60m2 mới tinh
dien_tich_moi = np.array([[60]])
gia_du_doan = model.predict(dien_tich_moi)

print(f"Giá nhà dự đoán cho căn hộ {dien_tich_moi[0][0]}m2 là: {gia_du_doan[0]:.2f} tỷ VNĐ")

5. Tổng kết

Dù các mô hình Deep Learning khổng lồ đang chiếm sóng trên các phương tiện truyền thông, các phương pháp Học máy kinh điển vẫn sống khỏe và là xương sống cho phần lớn hệ thống phân tích dữ liệu tại các tập đoàn lớn hiện nay. Chúng ghi điểm nhờ tốc độ cao, yêu cầu sức mạnh phần cứng thấp, cần ít dữ liệu hơn, và đặc biệt là khả năng diễn giải logic cực kỳ rõ ràng.

Cho dù mục tiêu của bạn là trở thành một Data Scientist chuyên nghiệp, một AI Engineer, hay chỉ đơn giản là một Lập trình viên muốn áp dụng AI vào phần mềm, thì việc nằm lòng Linear Regression, Decision Tree hay K-Means chính là bệ phóng vững chắc nhất dành cho bạn.

"Trí tuệ nhân tạo không phải là một loại phép thuật thần bí. Bản chất của nó chính là Toán học, Dữ liệu, và những thuật toán kinh điển được tinh chỉnh và tối ưu hóa đến mức nghệ thuật."

Nguồn tham khảo (References)

  • Geron, A. (2019). Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow (2nd Edition). O'Reilly Media.
  • Mitchell, T. M. (1997). Machine Learning. McGraw-Hill Science/Engineering/Math.
  • Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.
  • Tài liệu chuyên ngành tại thư viện trực tuyến của Scikit-Learn Documentation (scikit-learn.org).
  • Khái niệm chuẩn hóa từ khóa học "Machine Learning" do Giáo sư Andrew Ng (Đại học Stanford) giảng dạy trên nền tảng Coursera.

Khám phá các thư viện Python "đỉnh chóp" trong Khoa học dữ liệu (Data Science)

Khám phá các thư viện Python "đỉnh chóp" trong Khoa học dữ liệu (Data Science)

Chào các bạn! Nếu bạn đang bước những bước đầu tiên vào thế giới Khoa học dữ liệu (Data Science) hay Trí tuệ nhân tạo (AI), chắc hẳn bạn đã nghe đến cái tên Python. Python không chỉ dễ học mà còn sở hữu một hệ sinh thái vô cùng mạnh mẽ. Điểm làm nên sức mạnh thực sự của ngôn ngữ này chính là các thư viện Python chuyên dụng, giúp bạn phân tích dữ liệu và xây dựng mô hình Machine Learning chỉ trong vài dòng code.

Khám phá các thư viện Python "đỉnh chóp" trong Khoa học dữ liệu (Data Science)


Hôm nay, hãy cùng tìm hiểu những thư viện "xương sống" mà bất kỳ Data Scientist nào cũng phải nằm lòng nhé!

Mục lục

1. Tại sao Khoa học dữ liệu lại cần thư viện Python?

Trong Khoa học dữ liệu, chúng ta phải làm việc với hàng triệu, thậm chí hàng tỷ điểm dữ liệu. Nếu tự viết code từ đầu bằng các vòng lặp cơ bản để xử lý lượng dữ liệu này, chương trình của bạn sẽ chạy vô cùng chậm và dễ phát sinh lỗi. Các thư viện Python ra đời như những công cụ được tối ưu hóa sẵn (thường được viết bằng C hoặc C++ bên dưới) giúp thực hiện các phép toán phức tạp một cách chớp nhoáng.

2. NumPy: Nền tảng tính toán khoa học

NumPy (Numerical Python) là thư viện nền tảng cho hầu hết các công cụ Data Science khác. Chức năng chính của NumPy là hỗ trợ tính toán trên các mảng đa chiều (N-dimensional arrays) và ma trận, cùng với một tập hợp các hàm toán học cấp cao.

Cách sử dụng cơ bản: NumPy giúp bạn thực hiện các phép toán trên toàn bộ mảng dữ liệu mà không cần dùng đến vòng lặp for, một kỹ thuật gọi là Vectorization.

import numpy as np

# Tạo một mảng (array) từ list cơ bản
data = [1, 2, 3, 4, 5]
np_array = np.array(data)

# Nhân toàn bộ phần tử trong mảng cho 2 cực kỳ nhanh chóng
print(np_array * 2)
# Kết quả: [ 2  4  6  8 10 ]

3. Pandas: "Bậc thầy" thao tác và xử lý dữ liệu

Nếu NumPy làm việc tốt với các con số, thì Pandas lại là "vị vua" trong việc xử lý dữ liệu dạng bảng (tabular data), tương tự như Excel hay SQL. Cấu trúc dữ liệu quan trọng nhất của Pandas là DataFrame.

Trong quy trình Data Science, bạn sẽ dành đến 80% thời gian để làm sạch và chuẩn bị dữ liệu, và Pandas chính là trợ thủ đắc lực nhất cho công việc này.

import pandas as pd

# Tạo một DataFrame mô phỏng dữ liệu người dùng
data = {
    'Tên': ['An', 'Bình', 'Cường', 'Dung'],
    'Tuổi': [22, 25, 23, 28],
    'Nghề nghiệp': ['Sinh viên', 'Data Analyst', 'Developer', 'AI Engineer']
}
df = pd.DataFrame(data)

# Lọc ra những người trên 24 tuổi
nguoi_truong_thanh = df[df['Tuổi'] > 24]
print(nguoi_truong_thanh)

4. Matplotlib & Seaborn: Biến dữ liệu thành những bức tranh

Con người tiếp thu hình ảnh tốt hơn nhiều so với những con số khô khan. Để khám phá các quy luật ẩn sau dữ liệu (Data Visualization), chúng ta sử dụng Matplotlib và Seaborn.

  • Matplotlib: Cung cấp khả năng tùy biến biểu đồ ở mức độ chi tiết nhất.
  • Seaborn: Được xây dựng trên nền của Matplotlib, giúp vẽ các biểu đồ thống kê đẹp mắt, hiện đại chỉ với vài dòng code.
import matplotlib.pyplot as plt
import seaborn as sns

# Dữ liệu ví dụ
thang = ['Tháng 1', 'Tháng 2', 'Tháng 3', 'Tháng 4']
doanh_thu = [100, 150, 120, 200]

# Vẽ biểu đồ cột bằng Seaborn
sns.barplot(x=thang, y=doanh_thu, palette="viridis")
plt.title("Biểu đồ Doanh thu Quý 1")
plt.xlabel("Tháng")
plt.ylabel("Triệu VNĐ")
plt.show()

5. Scikit-Learn: Chìa khóa bước vào thế giới Machine Learning

Khi dữ liệu đã sạch sẽ và được thấu hiểu, bước tiếp theo là xây dựng các mô hình dự đoán. Scikit-Learn là thư viện tiêu chuẩn của Python dành cho Machine Learning. Nó cung cấp API nhất quán và dễ sử dụng cho vô số các thuật toán như Hồi quy tuyến tính (Linear Regression), Cây quyết định (Decision Trees), hay K-Means Clustering.

"Sức mạnh của Scikit-Learn nằm ở sự đơn giản. Bạn chỉ cần gọi hàm fit() để huấn luyện mô hình và predict() để đưa ra dự đoán."
from sklearn.linear_model import LinearRegression
import numpy as np

# Dữ liệu mô phỏng: Số giờ học (X) và Điểm số (y)
X = np.array([[1], [2], [3], [4], [5]])
y = np.array([3, 4, 5, 7, 8])

# Khởi tạo và huấn luyện mô hình
model = LinearRegression()
model.fit(X, y)

# Dự đoán điểm số nếu học 6 giờ
diem_du_doan = model.predict([[6]])
print(f"Điểm số dự đoán: {diem_du_doan[0]:.2f}")

6. Lời kết và Nguồn tham khảo

Hành trình chinh phục Khoa học dữ liệu và Trí tuệ nhân tạo là một chặng đường dài nhưng đầy thú vị. Việc làm chủ các thư viện Python như NumPy, Pandas, Matplotlib và Scikit-Learn chính là hành trang vững chắc nhất để bạn xây dựng những sản phẩm công nghệ tuyệt vời.

Nguồn tham khảo:

  • Tài liệu chính thức của NumPy: numpy.org
  • Tài liệu chính thức của Pandas: pandas.pydata.org
  • Hướng dẫn học Machine Learning với Scikit-Learn: scikit-learn.org
  • Python Data Science Handbook bởi Jake VanderPlas (O'Reilly Media).

Khoa học dữ liệu "công việc quyến rũ nhất thế kỷ 21"

Khoa Học Dữ Liệu Là Gì? Lộ Trình Trở Thành Kỹ Sư Phân Tích Dữ Liệu Cho Sinh Viên CNTT


Chào các bạn sinh viên ngành Công nghệ thông tin (CNTT)! Trong bối cảnh trí tuệ nhân tạo (AI) và dữ liệu lớn (Big Data) đang bùng nổ, "Khoa học dữ liệu" hay "Kỹ sư phân tích dữ liệu" đang là những từ khóa được săn đón nhất trên thị trường việc làm. Với lợi thế nền tảng lập trình sẵn có, sinh viên CNTT hoàn toàn có thể nắm bắt cơ hội này.
Vậy Khoa học dữ liệu là gì và đâu là lộ trình chuẩn xác để dấn thân vào con đường này? Hãy cùng tìm hiểu qua bài viết dưới đây nhé!

Khoa Học Dữ Liệu Là Gì? Lộ Trình Trở Thành Kỹ Sư Phân Tích Dữ Liệu Cho Sinh Viên CNTT



1. Khoa học dữ liệu (Data Science) là gì?
Khoa học dữ liệu là một lĩnh vực học thuật liên ngành, sử dụng các phương pháp khoa học, quy trình, thuật toán và hệ thống để trích xuất hoặc ngoại suy tri thức từ dữ liệu nhiễu, dữ liệu có cấu trúc và không có cấu trúc. Tạp chí Harvard Business Review từng gọi đây là "công việc quyến rũ nhất thế kỷ 21" nhờ mức độ quan trọng và mức lương vô cùng hấp dẫn.

Về bản chất, Khoa học dữ liệu là sự giao thoa giữa ba mảng chính: Khoa học máy tính (Computer Science), Toán học/Thống kê (Math/Statistics) và Kiến thức chuyên môn (Domain Expertise). Việc hiểu biết chuyên môn về một ngành cụ thể (như tài chính, y tế, e-commerce) sẽ giúp kỹ sư dữ liệu giải quyết đúng bài toán của doanh nghiệp đó.
Nhiệm vụ cốt lõi của một chuyên gia phân tích dữ liệu (Data Analyst) là kiểm tra, làm sạch, biến đổi và mô hình hóa dữ liệu để tìm ra các thông tin hữu ích hỗ trợ việc ra quyết định. Khi kết hợp với Machine Learning (Học máy), Khoa học dữ liệu mang lại khả năng dự đoán các kết quả có giá trị cao giúp doanh nghiệp tự động hóa và hành động thông minh hơn.
2. Lộ trình trở thành kỹ sư phân tích dữ liệu từ con số 0
Đối với sinh viên CNTT, các bạn đã có sẵn lợi thế về tư duy logic. Dưới đây là 5 bước trọng tâm bạn cần chinh phục:
Bước 1: Củng cố nền tảng Toán học Toán học là cốt lõi của dữ liệu. Bạn cần ôn lại 4 mảng chính: Xác suất, Thống kê, Đại số tuyến tính và Giải tích.
  • Xác suất và Thống kê: Hỗ trợ bạn đánh giá độ chính xác, sai số và ý nghĩa của các dự đoán trong tương lai.
  • Đại số tuyến tính và Giải tích: Giúp bạn hiểu được cơ chế hoạt động của các thuật toán Machine Learning và cách xử lý các ma trận dữ liệu đa chiều.
Bước 2: Nắm vững Ngôn ngữ lập trình và Thư viện xử lý dữ liệu Python là ngôn ngữ phổ biến nhất trong ngành Khoa học dữ liệu nhờ cú pháp thân thiện và hệ sinh thái thư viện phong phú. Bạn cần nắm vững:
  • NumPy và Pandas: Để thao tác với các mảng đa chiều và xử lý các tệp dữ liệu phức tạp (như CSV, JSON).
  • Matplotlib và Seaborn: Đây là các thư viện trực quan hóa dữ liệu (Data Visualization). Matplotlib đóng vai trò là "động cơ" cốt lõi cho mọi biểu đồ, trong khi Seaborn cung cấp các biểu đồ thống kê đẹp mắt, chuyên nghiệp chỉ với vài dòng code.
Bước 3: Thành thạo SQL và Hệ quản trị Cơ sở dữ liệu Khi làm việc với hàng triệu dòng dữ liệu, Excel sẽ lập tức quá tải. Đó là lý do bạn bắt buộc phải học SQL (Structured Query Language) để truy vấn, cập nhật và thao tác với dữ liệu trong các Hệ quản trị cơ sở dữ liệu quan hệ (RDBMS) như PostgreSQL, MySQL hay SQL Server SQL được thiết kế khá giống tiếng Anh nên rất dễ tiếp cận và mang lại ROI (tỷ suất hoàn vốn) cao nhất cho thời gian học tập của bạn.
Bước 4: Machine Learning (Học máy) và Feature Engineering Sau khi làm sạch dữ liệu, bạn sẽ xây dựng mô hình. Kỹ thuật quan trọng nhất ở bước này là Feature Engineering (Trích xuất đặc trưng) – nghệ thuật biến đổi dữ liệu thô thành các biến có ý nghĩa giúp mô hình học các mẫu (patterns) tốt hơn. Đồng thời, bạn cần làm quen với Framework Scikit-learn để xây dựng các mô hình:
  • Học có giám sát (Supervised Learning): Dùng dữ liệu đã được gán nhãn để dự đoán kết quả, với các thuật toán như Hồi quy tuyến tính (Linear Regression), Cây quyết định (Decision Tree), K-Nearest Neighbors.
  • Học không giám sát (Unsupervised Learning): Khám phá dữ liệu không được gán nhãn để gom cụm (Clustering) và tìm luật kết hợp.
Bước 5: Kỹ năng phần mềm và Khả năng "Google" Khi làm việc thực tế, bạn phải biết dùng Git để quản lý mã nguồn, và Docker để đóng gói (containerize) mô hình AI, giúp quá trình triển khai (deploy) sản phẩm lên server mượt mà hơn. Đặc biệt, kỹ năng tự tìm kiếm và gỡ lỗi bằng Google (hay các AI trợ lý) là vũ khí giúp bạn sinh tồn và làm chủ công nghệ mới một cách chủ động.
3. Xây dựng Portfolio - Chìa khóa chinh phục nhà tuyển dụng
Trong thị trường cạnh tranh, một bản CV liệt kê kỹ năng là chưa đủ. Bạn cần một Data Science Portfolio chứa các dự án thực tế để trực tiếp chứng minh năng lực.
  • Không dùng dữ liệu "đồ chơi" (Toy datasets): Tránh xa các tập dữ liệu quá cơ bản như Titanic hay Iris. Hãy đi tìm các bộ dữ liệu thực tế liên quan đến ngành nghề bạn muốn ứng tuyển (ví dụ: dự đoán tỷ lệ khách hàng rời bỏ của trang e-commerce, phân tích dữ liệu y tế)
  • Dữ liệu thực tế thường lộn xộn: Hãy cho nhà tuyển dụng thấy khả năng thu thập dữ liệu (scraping), xử lý dữ liệu thiếu hụt và ngoại lệ của bạn. Khâu làm sạch dữ liệu thường chiếm 80% thời gian của một dự án.
  • Kể chuyện với dữ liệu (Data Storytelling): Đưa code lên GitHub cần đi kèm với một file README được viết cẩn thận. Hãy trình bày rõ vấn đề kinh doanh là gì, bạn đã giải quyết ra sao, và kết luận kinh doanh mang lại được điều gì. Việc code rành mạch và truyền đạt thông tin tốt cho người "không chuyên về kỹ thuật" chính là điểm cộng lớn nhất.
Kết luận
Hành trình trở thành kỹ sư phân tích dữ liệu hay Data Scientist đòi hỏi sự giao thoa của rất nhiều kỹ năng từ lập trình, toán học cho đến tư duy nhạy bén về kinh doanh. Với xuất phát điểm là sinh viên CNTT, các bạn đã có trong tay chiếc chìa khóa quan trọng nhất. Hãy bắt đầu ôn lại toán, mở trình soạn thảo code Python lên, học hỏi SQL và xây dựng dự án portfolio đầu tiên cho riêng mình ngay hôm nay nhé! Chúc các bạn thành công!

Tổng quan về bài toán tóm tắt dữ liệu bằng ngôn ngữ (Linguistic Summarization - LS) dựa trên các tài liệu đã cung cấp.

1. Mốc thời gian và các nhóm tác giả tiêu biểu

Bài toán tóm tắt dữ liệu bằng ngôn ngữ (Linguistic Summarization - LS) đã trải qua hơn 4 thập kỷ phát triển, đi từ những ý tưởng nền tảng đến các ứng dụng phức tạp:

  • Năm 1982: R.R. Yager lần đầu tiên đề xuất khái niệm tóm tắt dữ liệu bằng ngôn ngữ dựa trên lý thuyết tập mờ của L.A. Zadeh.
  • Thập niên 1990 - 2000: Nhóm tác giả J. Kacprzyk, R.R. Yager và S. Zadrożny đóng vai trò tiên phong trong việc đưa lý thuyết vào thực tiễn thông qua các "protoform" (dạng mẫu câu), ứng dụng hiệu quả trong cơ sở dữ liệu quan hệ và hỗ trợ quyết định kinh doanh.
  • Giai đoạn 2005 - 2008: LS mở rộng từ dữ liệu tĩnh sang chuỗi thời gian (time series) bởi nhóm J. Kacprzyk, A. Wilbik. Đồng thời, hệ thống SAINTETIQ (Bosc, Dubois, Prade) phát triển triết lý tóm tắt phân cấp.
  • 2008 - 2011: A. Niewiadomski, D. Wu và J.M. Mendel mở rộng mô hình sang tập mờ loại 2 (Type-2 FS) nhằm xử lý tốt hơn sự không chắc chắn của ngôn từ.
  • 2011 - Nay: Hướng tối ưu hóa phát triển mạnh mẽ với các thuật toán siêu heuristic (GA, ACO) bởi R. Castillo-Ortega và cộng sự.
  • 2015 - Nay: Nhóm tác giả Việt Nam (Nguyễn Cát Hồ, Phạm Thị Lan, Phạm Đình Phong) đề xuất sử dụng Đại số gia tử (Hedge Algebra), giải quyết các hạn chế về ngữ nghĩa chủ quan của tập mờ truyền thống.



2. Các phương pháp tiếp cận và nền tảng lý thuyết

Các nghiên cứu về LS hiện nay tập trung vào bốn nền tảng toán học và thuật toán chủ đạo:

  • Lý thuyết tập mờ và Protoform: Tính toán độ đúng đắn ($truth$ $degree$) của các câu chứa từ lượng hóa mờ và tính từ mờ.
  • Sinh ngôn ngữ tự nhiên (NLG): Kết hợp suy luận mờ với kỹ thuật NLG để tạo ra báo cáo tự nhiên hơn thay vì các khuôn mẫu cứng nhắc.
  • Tối ưu hóa và Siêu heuristic: Sử dụng Giải thuật di truyền (GA), Tối ưu hóa bầy đàn (PSO) để tìm kiếm câu tóm tắt tốt nhất trong không gian tìm kiếm khổng lồ.
  • Đại số gia tử (Hedge Algebra): Giải quyết vấn đề cấu trúc đa ngữ nghĩa, giảm sự phụ thuộc vào trực giác con người khi định nghĩa hàm liên thuộc.

3. Ứng dụng thực tiễn

Lĩnh vực Ứng dụng cụ thể
Kinh doanh & Tài chính Phân tích xu hướng giá cổ phiếu, tóm tắt dữ liệu bán hàng, đánh giá hiệu suất quỹ đầu tư.
Y tế Hệ thống BabyTalk (chăm sóc trẻ sơ sinh), theo dõi người cao tuổi qua cảm biến, phân tích nhịp tim.
Kỹ thuật & Khí tượng Phân tích log máy chủ, sinh báo cáo thời tiết tự động (SumTime-Mousam, GALIWeather).
Giáo dục Tóm tắt dữ liệu học tập hỗn hợp (blended learning) từ hệ thống LMS.

4. Những thành tựu đã được giải quyết

Hệ thống tóm tắt ngôn ngữ hiện nay đã đạt được những bước tiến quan trọng trong việc chuẩn hóa cấu trúc và tối ưu hiệu năng.
  • Định hình bộ khung toán học: Xây dựng thành công mô hình protoform chuẩn "Q y are S" và các biến thể điều kiện.
  • Mở rộng sang dữ liệu động: Xử lý tốt các đặc trưng của chuỗi thời gian như xu hướng và độ biến động.
  • Đề xuất tiêu chí đánh giá: Ngoài độ đúng, các độ đo như độ bao phủ, độ đặc tả và tính thông tin giúp chọn lọc câu tóm tắt chất lượng cao.
  • Giảm thiểu không gian tìm kiếm: Áp dụng hiệu quả thuật toán Apriori và chiến lược Greedy để loại bỏ các câu vô nghĩa, tăng tốc độ xử lý.

5. Những vấn đề tồn tại và hướng nghiên cứu mở

Bên cạnh những thành tựu, LS vẫn đối mặt với nhiều thách thức lớn:

  1. Hạn chế về tính diễn giải chủ quan: Sự phụ thuộc vào trực giác khi định nghĩa hàm liên thuộc vẫn là thách thức về tính phổ quát.
  2. Xử lý Big Data & Streaming Data: Chi phí tính toán cho việc sinh tóm tắt theo thời gian thực trên luồng dữ liệu cực lớn vẫn rất cao.
  3. Sự dư thừa thông tin (Redundancy): Vấn đề trích xuất tập hợp câu tóm tắt tối ưu nhất mà không bị trùng lặp ý nghĩa chưa được giải quyết triệt để.
  4. Rào cản đa ngôn ngữ: Thiếu hụt các hệ thống hỗ trợ đa ngôn ngữ hoặc thích ứng xuyên ngôn ngữ (Cross-lingual).
  5. Tích hợp XAI và Học sâu: Kết hợp khả năng của Deep Learning với cấu trúc diễn giải của LS để tạo ra hệ thống AI minh bạch.
  6. Quan hệ nhân quả (Causal relations): Khả năng dùng LS để trả lời câu hỏi "tại sao" trong dữ liệu quy trình vẫn còn đang bỏ ngỏ.

ML 1 _ Tổng quan về Machine Learning (Học máy)

Tổng quan về Machine Learning (Học máy)

Thời gian gần đây, Trí tuệ nhân tạo (AI) hay cụ thể hơn là Machine Learning (ML) được nhắc tới như là phần cốt lõi của các hệ thống thông minh. Rất nhiều những sản phẩm, giải pháp công nghệ được ứng dụng AI, có thể kể đến một số sản phẩm tiêu biểu đã làm thay đổi cách nhìn về AI nói chung và Machine learning nói riêng như:
 - Xe tự hành của Google và Tesla, 
 - Hệ thống tự tag khuôn mặt trong ảnh của Facebook, 
 - Trợ lý ảo Siri của Apple, 
 - Hệ thống gợi ý sản phẩm của Amazon, 
 - Hệ thống gợi ý phim của Netflix, 
 - Máy chơi cờ vây AlphaGo, AlphaGo Zero của Google DeepMind, …, 
 -  Jarvis - trợ lý thông minh cho căn nhà của Mark Zuckerberg
 ... ngoài ra, còn vô số các ứng dụng khác trong các sản phẩn tích hợp. [1]

Theo định nghĩa của Wikipedia, Machine learning is the subfield of computer science that “gives computers the ability to learn without being explicitly programmed”. Nói đơn giản, Machine Learning là một lĩnh vực nhỏ của Khoa Học Máy Tính, nó có khả năng tự học hỏi dựa trên dữ liệu đưa vào mà không cần phải được lập trình cụ thể.

Qua các lịch sử phát triển và các lĩnh vực phát triển, có thể hiểu machine learning là  "tập con" của AI. Xuất phát từ thực tiễn, nhu cầu tính toán, phân tích trên dữ liệu có kích thước lớn (big data) ngày càng cao, cộng với sự phát triển nhanh chóng của công nghệ phần cứng dẫn tới hiệu năng tính toán của máy tính ngày càng cao.  Điều này đã thúc đầy machine learning tiến thêm một bước đột phá mới gọi là Deep learning (tạm hiểu là học sâu). Với bước tiến nhảy vọt này, máy tính đã có thể giải quyết được những bài toán và trước đó tưởng trừng như không thể như: phân loại cả ngàn vật thể khác nhau trong các bức ảnh, tự tạo chú thích cho ảnh, bắt chước giọng nói và chữ viết của con người, giao tiếp với con người, hay thậm chí cả sáng tác văn hay âm nhạc (Xem thêm 8 Inspirational Applications of Deep Learning) [1]

Mối quan hệ giữa AI, Machine Learning và Deep Learning.
Mối quan hệ giữa AI, Machine Learning và Deep Learning.

Trong bối cảnh đó, tại Việt Nam những nghiên cứu và ứng dụng AI hay Machine learning còn khá khiêm tốn, chưa kể đến việc đào tạo nguồn nhân lực chất lượng cao cho lĩnh vực này còn thiếu và yếu. Đây thực sự là cơ hội và thách thức không nhỏ đối với các cơ sở đào tạo. Rất mong các bạn sinh viên, đặc biệt là các bạn sinh viên CNTT quan tâm nghiên cứu sâu về lĩnh vực này - một lĩnh vực cốt lõi của cuộc cách mạng 4.0.

#
Tham khảo:

[1]  Bài 1: Giới thiệu về Machine Learning - Blog: machinelearningcoban.com - Truy cập: 22.10.19 

Gợi ý để bắt đầu học lập trình Trí tuệ nhân tạo (AI programming)

6 gợi ý để bắt đầu học lập trình trí tuệ nhân tạo (AI programming)

Trí tuệ nhân tạo hay trí thông minh nhân tạo (Artificial Intelligence hay Machine Intelligence - AI) là một ngành thuộc lĩnh vực khoa học máy tính (Computer Science).

Với xu thế của cuộc cách mạng công nghiệp 4.0 đang bùng nổ, có khá nhiều lập trình mong muốn được học và phát triển năng lực bản thân trong mảng này.

Gợi ý để bắt đầu học lập trình Trí tuệ nhân tạo (AI programming)
Gợi ý để bắt đầu học lập trình Trí tuệ nhân tạo (AI programming)


Vậy nên bắt đầu thế nào? 

Hãy thử tham khảo 6 bước sau xem sao:

Bước 1: Tìm hiểu về Python và Các hệ quản trị cơ sở dữ liệu (SQL, Oracle,...)

Điều cốt yếu mà bạn phải làm là phải học một ngôn ngữ lập trình. Mặc dù trong thực tế có rất nhiều ngôn ngữ mà bạn có thể bắt đầu, nhưng Python là sự lựa chọn tốt nhất vì các thư viện của nó phù hợp hơn với Machine Learning.


Bạn có thể tham khảo các liên kết dưới đây:

 Machine Learning with Text in scikit-learn (PyCon 2016) 

Machine learning in Python with scikit-learn 

Machine learning with Python 

Machine Learning Part 1 | SciPy 2016 Tutorial 


Bước 2: Học trí tuệ nhân tạo từ một số khóa học dưới đây

Artificial Intelligence: Principles and Techniques from Stanford - Một chương trình giáo dục xuất sắc cho những học giả, những người được truyền cảm hứng bằng cách làm quen nhiều hơn về AI. Khóa học tập trung vào các tiêu chuẩn cơ bản của AI.



CS405: ARTIFICIAL INTELLIGENCE: Giới thiệu lĩnh vực trí tuệ nhân tạo (AI). Các tài liệu về lập trình AI, logic, tìm kiếm, chơi trò chơi, nghiên cứu máy móc, hiểu ngôn ngữ tự nhiên và robot giới thiệu với sinh viên về phương pháp AI, công cụ và kỹ thuật, ứng dụng đối với các vấn đề tính toán và vai trò của AI.



edx.org course on AI: Khóa học này cung cấp các nguyên tắc cơ bản của Artificial Intelligence (AI) và cách áp dụng chúng. Thiết kế các intelligent agent để giải quyết các vấn đề trong thế giới thực bao gồm tìm kiếm, trò chơi, nghiên cứu máy móc, logic và sự hạn chế trong các vấn đề.



MIT’s course on AI: Khóa học này giới thiệu cho sinh viên kiến thức cơ bản, giải quyết vấn đề và phương pháp học tập của trí tuệ nhân tạo. Sau khi hoàn thành khóa học này, sinh viên sẽ có thể phát triển các hệ thống thông minh bằng cách ứng dụng các giải pháp cho các vấn đề tính toán cụ thể; hiểu vai trò của lập trình tri thức, giải quyết vấn đề và học tập trong hệ thống kỹ thuật thông minh. Khóa học đánh giá cao vai trò của việc giải quyết vấn đề, tầm nhìn và ngôn ngữ trong việc hiểu trí tuệ thông minh của con người từ góc độ tính toán.



Learn the Fundamentals of AI - Khóa học trực tuyến này, được chia thành 10 bài học, giúp sinh viên hiểu rõ hơn về vũ trụ AI. Để hiểu nó, hãy đảm bảo bạn có một số thông tin cần thiết về toán học dựa trên biến trực tiếp và giả thuyết khả năng. Bạn nên học cách ghi nhớ mục tiêu cuối cùng để chuẩn bị trước.



Berkeley Video Lecturers: Khóa học bao gồm các bài giảng bằng video.

Trên đây là 6 khóa học về trí tuệ nhân tạo hàng đầu cho người mới bắt đầu và nâng cao. Hy vọng chúng sẽ hữu ích cho bạn.


Bước 3: Tìm hiểu kiến thức cơ bản về lý thuyết xác suất, thống kê và Toán học

Bạn có thể tham khảo các liên kết dưới đây:



Đại số tuyến tính
- Linear Algebra
- MIT 18.06 Đại số tuyến tính của Gilbert Strang 

(Link tham khảo: https://www.youtube.com/watch?list=PLE7DDD91010BC51F8&v=ZK3O402wf1c)



Lý thuyết xác suất và thống kê
- Probability and Statistics
- MIT 6.041

Phân tích hệ số xác suất và xác suất ứng dụng của John Tsitsiklis 

(Link tham khảo: https://www.youtube.com/watch?list=PLUl4u3cNGP61MdtwGTqZA0MreSaDybji8&v=j9WZyLZCBzs)



Calculus (Link tham khảo: http://kisonecat.com/teaching/2013/calculus-one/)



Multivariate Calculus (Link tham khảo: http://kisonecat.com/teaching/2014/m2o2c2/)

Graph theory (Link tham khảo: https://class.coursera.org/pgm-003)



Optimization methods (Link tham khảo: https://online.stanford.edu/courses)

Bước 4: Đọc sách


http://aima.cs.berkeley.edu/



Artificial Intelligence: A Modern Approach, của Stuart J. Russell và Peter Norvig 

http://wps.aw.com/wps/media/objects/5771/5909832/PDF/Luger_0136070477_1.pdf



The Quest for Artificial Intelligence của Nils J. Nilsson

(Link tham khảo: http://ai.stanford.edu/~nilsson/QAI/qai.pdf)



Practical Artificial Intelligence: Programming in Java của Mark Watson 

(Link tham khảo: https://www.saylor.org/site/wp-content/uploads/2011/11/CS405-1.1-WATSON.pdf)


https://grey.colorado.edu/CompCogNeuro/index.php/CCNBook/

Main

Simply Logical: Intelligent Reasoning by Example của Peter Flach

 (Link tham khảo: https://www.cs.bris.ac.uk/~flach/SL/SL.pdf)



The AI Revolution: Road to Superintelligence 

(Link tham khảo: https://waitbutwhy.com/2015/01/artificial-intelligence-revolution-1.html)


http://psych.colorado.edu/~oreilly/comp_ex_cog_neuro.html

Bước 5: Thực hành 

Khi bạn có một sự hiểu biết đầy đủ về ngôn ngữ lập trình ưa thích của mình và thực hành đủ với các yếu tố cần thiết, bạn nên bắt đầu tìm hiểu thêm về Machine Learning.
Trong Python, bắt đầu học các thư viện Scikit-learning, NLTK, SciPy, PyBrain và Numpy sẽ có giá trị trong khi soạn các thuật toán Machine Learning.



Thực hành vài bài tập về Scikit từ trang web:

http://scikit-learn.org/ và https://www.edx.org/course/artificial-intelligence-ai-columbiax-csmm-101x-0 (dành cho các bài tập thực hành bằng Python).



Ngoài ra ở đây là một bản tóm tắt các tài liệu để để tìm hiểu và trau dồi Machine Learning:



http://www.r2d3.us/visual-intro-to-machine-learning-part-1/



https://www.coursera.org/learn/machine-learning



https://www.cs.cmu.edu/~tom/10701_sp11/lectures.shtml



https://code.tutsplus.com/tutorials/how-to-build-a-python-bot-that-can-play-web-games–active-11117



https://www.udacity.com/course/intro-to-artificial-intelligence–cs271



https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/

Bước 6: Thực hành — Học — Tự mình thực hành


Với trình tự này, từng bước một, bạn sẽ từ từ trở thành một lập trình viên AI.



Một khi tất cả 6 bước được thực hiện, bạn đã có thể tự tin để bắt đầu với AI/ML rồi.

Chúc bạn thành công!



#

[Algorithm] Thuật toán leo đồi (Hill Climbing Search)

Giơi thiệu Thuật toán leo đồi (Hill Climbing Search)



Trước hết, ta nghiên cứu bài toán sau: Trò chơi n2-1 số (n thuộc N, n > 1).

Bài toán:


 Có n2-1 số mang các giá trị từ 1 tới n2-1 được sắp xếp vào một lưới các ô vuông kích thước n x n. Mỗi số đó được gọi là một quân cờ và lưới ô đó được gọi là bàn cờ. Có một vị trí của bàn cờ bỏ trống. Mỗi lần di chuyển quân, người chơi được phép chuyển một quân ở vị trí ô tiếp giáp cạnh với ô trống vào ô trống.

Yêu cầu: 


Từ một trạng thái ban đầu (sự sắp xếp ban đầu của các quân trên bàn cờ), hãy thực hiện các nước đi hợp lệ để thu được trạng thái kết thúc (trạng thái đích cần đạt được).

Vídụ: với trò chơi 8 số ta minh họa trạng thái ban đầu và trạng thái kết thúc qua các hình vẽ dưới đây:

Hình 1


Để giải bài toán này, chúng ta sẽ nghĩ ngay tới việc xây dựng một cây tìm kiếm mà gốc của cây tương ứng với trạng thái xuất phát của bàn cờ. Các đỉnh khác của cây tương ứng với các trạng thái thu được do việc thực hiện các nước đi hợp lệ (các nước đi được phép thực hiện là: lên trên, xuống dưới, sang trái và sang phải). Với ví dụ trên, ta có cây tìm kiếm sau:
Hình 2

 Tiếp đó, ta chỉ việc áp dụng các thuật toán thông dụng như: thuật toán tìm kiếm theo chiều rộng hoặc thuật toán tìm kiếm theo chiều sâu để tìm ra lời giải.

Ý tưởng thuật toán:

Việc suy nghĩ như trên xem ra có tính khả thi (đơn giản, dễ cài đặt), tuy nhiên, dễ nhận thấy rằng nếu số n lớn hơn, ta sẽ phải phát triển một số quá lớn các trạng thái trước khi phát hiện ra trạng thái đích. Những hạn chế về mặt thời gian và dung lượng bộ nhớ không cho phépthực hiện điều đó.

Trong thực tế, có nhiều bài toán mà số các trạng thái của nó là rất lớn (như cờ vua, cờ tướng...), thì việc giải bài toán chỉ có thể thực hiện nếu bằng một cách nào đó ta lược bỏ những trạng thái thừa, không cần thiết nhằm giảm số lượng trạng thái cần phát triển. Để làm được điều đó, phải sử dụng khéo léo các thông tin phản hồi nảy sinh trong quá trình tìm kiếm (các thông tin này còn gọi là thông tin cảm tính: HeuristicInformation). Cách làm này được đưa ra nhằm mục đích lựa chọn được hướng tìm kiếm tốt nhất tại mỗi bước theo nghĩa: hướng đi đó nhanh dẫn tới trạng thái đích nhất và nhằm giảm công sức tìm kiếm.


Thuật toán leo đồi:

Thuật toán tìm kiếm leo đồi đã đáp ứng được yêu cầu trên. Nội dung thuật toán được mô tả như sau:

Bước 1: Nếu trạng thái đầu trùngvới trạng thái đích thì dừng ngay, ngược lại thì chuyển sang bước 2.

Bước 2: Sử dụng các quy tắc biến đổi để tạo ra 1 tập hợp các trạng thái từ trạng thái hiện thời (trong bài toán trên ta có 4 quy tắc biến đổi tương ứngvới 4 phép di chuyển quân).

Bước 3: Với mỗi trạng thái trong tập hợp vừa tạo ra kiểm tra xem đó có phải là trạng thái đích hay không? Nếu phải thì ngừng việc tìm kiếm, nếu không phải thì ta kiểm tra xem trạng thái mới này có tốt hơn (gần trạng thái đích hơn) so với trạng thái đã có hay không? Nếu quả thật như vậy thì ghi nhận trạng thái này, ngược lại thì bỏ qua.

Bước 4: Trong các trạng thái được tạo ra (sau khi thực hiện các thao tác ở bước 3), ta ưu tiên phát triển trạngthái tốt nhất (trạng thái tốt nhất là trạng thái có tiềm năng dẫn tới đích nhanh nhất).
Bước này nhằm mục đích chuyển hướng tìm kiếm lời giải nhanh đến đích nhất.

Bước 5: Lặp lại từ bước 2.

Đến đây bạn có thể nhận thấy thuật toán tìm kiếm leo đồi thực chất là thuật toán tìm kiếm theo chiều sâu, song tại mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đích nhất để phát triển trước. Vấn đề quan trọng là ở chỗ biết khai thác khéo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhanh quá trình tìm kiếm.Thông thường ta gắn mỗi trạng thái của bài toán với một số đo (1 hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó.

Như vậy: Nếu trạng thái hiện thời là u, theo bước 4 của thuật toán trên thì trạng thái v sẽ được phát triển tiếp theo nếu vẻ kề(u) và hàm đánh giá của v đạt giá trị max (hoặc min).


Phần tiếp theo sẽ trình bày cụ thể thuật toán để giải bài toán trên. Trong bài toán này, ta sẽ sử dụng hàm đánh giá ký hiệu là h với ý nghĩa: h(u) cho biết số cácchữ số trong trạng thái u không trùng với vị trí của nó trong trạng thái đích.Trạng thái có tiềm năng dẫn tới đích nhanh nhất (được ưu tiên phát triển trước)là trạng thái có hàm đánh giá h đạt giá trị min.
Thuật toán cho trò chơi n2-1 số được mô tả như sau :
Hình 3


Algorithm:


Input: Trạng thái ban đầu u0và trạng thái đích ut

BEGIN

1. P:={u0} ; { P để lưu các trạng thái chờ phát triển được tổ chức dưới dạng Stack }

   Q:=Φ ;  { để lưu các trạng thái đãphát triển được tổ chức dưới dạng hàng đợi Queue }

   P:= Φ ; { P để lưu tạm thời các trạngthái kề với trạng thái đang xét }

   found:=false;

2. While (P # y) and (not found) do

   2.1. Loại bỏ trạng thái u ở đỉnh stack P và đặt nó vào hàng đợi Q:
          Pop(P, u);
          Add(u, Q);

2.2. if u=ut then found:= true
       else
           For v kề (u) do
              if (v thuộc P U Q) and (h(v) <= max { h(w)| w thuộc P U Q } then
               Begin
                  father (v):=u;
                  Add (v, P);
              End;

        if P <> f then
         Begin
           - Sắp xếp các trạng thái trong P theotrật tự tăng của hàm h;
           - Chuyển các trạng thái trong P vàođỉnh của stack P sao cho trạng thái có giá trị hàm h nhỏ nhất ở đỉnh của P;

         End;

END.

Output:  

- Nếu found = false thì bài toán không có lời giải.

- Nếu found = true thì lời giải là đường đi từ u0 tới ut được xác định bằng cách sử dụng hàm father.


Chú ý: Sau khi chuyển các trạng thái từ P vào P thì P= f



 Hình 4

h(v1)  ≤  h(v2)  ≤ .... ≤  h(vk)

Với ví dụ trên, cây tìm kiếm được hình thành bởi tìm kiếm leo đồi có các trạng thái được phát triển như hình vẽ dưới (nét đậm thể hiện hướng tìm kiếm), các số ghi cạnh mỗi đỉnh là giá trị của hàm h tại đỉnh đó.

Thuật toán này có tên gọi là thuật toán tìm kiếm leo đồi, vì tư tưởng của nó tương tự như trường hợp: Một người ở vị trí chân đồi u0 và muốn leo lên đỉnh đồi tại vị trí ut. Anh ta chọn một đỉnh cao nhất trong số các đỉnh mà anh ta có thể đến được (từ vị trí đang đứng) để leo lên, tại vị trí này anh ta lại chọn một đỉnh cao nhất như bước trước để leo lên. Quá trình cứ lặp lại như vậy cho đến khi tới được đích ut.

Nhận xét: Thuật toán này đơn giản, dễ cài đặt và tỏ ra có nhiều hiệu quả. Bạn đọc có thể tự lập trình để giải bài toán trên, kết quả khá tuyệt vời! Tuy nhiên, thuật toán này không phù hợp với các bài toán có giá trị hàm đánh giá đột nhiên thay đổi khi đến ngưỡng nào đó. Một số hiện tượng sẽ nảy sinh trong quá trình tìm kiếm được ghi nhận như sau:

*Có cực đại địa phương, là nơi đạt được lời giải tốt hơn các lời giải lân cận, nhưng chưa phải là lời giải tốt trên tổng thể. Như vậy phải có biện pháp ghi nhớ lại nhiều đường đi đề phòng khi cần đi lại đường cũ.

*Có vùng lời giải như cao nguyên bằng phẳng, không thể xác định được ngay hướng nào tốt hơn nếu chỉ so sánh vùng lân cận (các trạng thái của bài toán có hàm đánh giá xấp xỉ bằng nhau). Khi đó cần có bước nhảy xa để thoát khỏi vùng bằng phẳng.

Có đỉnh hình chóp, đó là trạng thái được lựa chọn tốt hơn vùng lân cận nhưng không vượt qua được theo bất kỳ hướng nào. Để xử lý hiện tượng này, nên chuyển theo đồng thời vài hướng.

Cực đại địa phương Cao nguyên Chóp

Minh họa cực trị địa phương khi giải bài toán bằng thuật toán leo đồi.

Như vậy: Thuật toán này chỉ làphương pháp giải quyết cục bộ, để tăng tính tối ưu, có thể sử dụng phối hợp nóvới các thuật toán tìm kiếm khác.

 Hình 5


Tham khảo 123doc



Categories

AI (23) AI programming (1) ASP (1) Android (32) Assembly (17) Biểu diễn thuật toán (1) Bubble-Sort (1) Bài giảng (2) Bài giảng lập trình C và Cpp (21) Bài viết hay (111) Bản đồ tư duy (1) C Plus Plus (102) C/C++ (16) CDSL phân tán (1) CSS (2) Cơ sở dữ liệu (11) Danh ngôn lập trình (1) Datamining (4) Genetic Algorithm (1) Giáo trình (3) Giải thuật tiến hóa - thuật toán di truyền (2) Google App Engine (2) Góc học tập (34) HTML (1) Hướng dẫn sử dụng Emu8086 (1) Học lập trình (133) Học lập trình C và CPP qua ví dụ (17) Java (54) Java Căn bản (6) JavaScript (5) Kỹ năng đọc hiệu quả (1) Kỹ thuật lập trình (16) Kỹ thuật đồ họa máy tính (10) Lý thuyết Cơ sở dữ liệu (2) Lý thuyết đồ thị (10) Lập trình Cơ sở dữ liệu (2) Lập trình Python (2) Lập trình căn bản (8) Lập trình hướng đối tượng với Java (7) Lập trình mobile (9) Lập trình mạng (6) Lập trình nhúng (1) Lập trình trí tuệ nhân tạo (2) ML (1) MS Access (1) Machine learning (6) Mạng máy tính (1) Mẹo tìm kiếm trên Google (1) Nghiên cứu khoa học (5) Ngôn ngữ lập trình (2) Những cuốn sách hay mà bạn nên đọc khi còn trẻ (1) Pascal (3) Phương pháp tính toán tối ưu (2) Phương pháp tối ưu (2) Quản lý dự án CNTT (1) SQL (5) Swift (9) Sách hay (4) Thiết kế Web (2) Thuật toán (50) Thuật toán Sắp Xếp -Sort (9) Thuật toán Tìm kiếm - Search (5) Thuật toán di truyền (4) Thực hành Android (2) Tin học văn phòng (5) Tiện ích máy tính (2) Toán rời rạc (12) Trí tuệ nhân tạo (24) Tài liệu tham khảo (3) Tìm hiểu Blockchain (2) Tự học Android (3) Tự học Android qua ví dụ (1) Tự học JavaScript (1) Tự học lập trình (9) Tự học lập trình Android (17) Tự học lập trình C và CPP (14) Tự học lập trình java qua các ví dụ (8) XML (1) blockchain (2) bài giảng quản lý dự án CNTT (1) bài tập java (3) bài tập lập trình (4) cấu trúc dữ liệu giải thuật (15) hướng dẫn viết báo (1) học lập trình Java (11) học máy (7) hợp ngữ (8) lập trình viên (5) phưng pháp đơn hình (2) thuật toán AI (2) tài liệu CNTT miễn phí (2) tính toán tối ưu (1) tự học lập trình iOS (8) tự học lập trình python (1) ví dụ Assembly (1) Đại số gia tử và ứng dụng (1) Đồ họa (4)