Kỹ thuật khai phá dữ liệu: K-means · DBSCAN · SVM

1. Tổng quan

A. Định nghĩa

Khai phá dữ liệu (Data Mining) là bước cốt lõi của quá trình khám phá tri thức (KDD, Knowledge Discovery in Databases) nhằm phát hiện các mẫu·quy tắc·tri thức có ý nghĩa mà con người khó biết trước từ lượng dữ liệu lớn; chủ đề này đề cập đến các thuật toán tiêu biểu phân cụm (Clustering: K-means·DBSCAN) và phân loại (Classification: SVM).

Cửa ngõ đầu tiên để hiểu khai phá dữ liệu là trục 'có hay không có đáp án (nhãn)'. Nếu dữ liệu huấn luyện có gắn đáp án, việc học ranh giới để mô phỏng đáp án đó là học có giám sát (Supervised Learning); còn nếu không có đáp án mà chỉ dựa vào độ tương tự của bản thân dữ liệu để phát hiện cấu trúc thì là học không giám sát (Unsupervised Learning). K-means và DBSCAN là phân cụm không giám sát, gom những thứ giống nhau mà không cần đáp án; SVM là phân loại có giám sát, học đáp án để vạch ranh giới chia hai lớp. Học ba kỹ thuật trong một chủ đề giúp tổng hợp trong một cái nhìn cách thuật toán rẽ nhánh tùy thuộc 'khi có và khi không có đáp án, và định nghĩa độ tương tự bằng gì'.

Cửa ngõ thứ hai là 'định nghĩa độ tương tự', điểm lại rẽ nhánh bên trong phân cụm. K-means theo tư duy dựa trên khoảng cách (distance) "những điểm gần tâm cụm thì gom lại", còn DBSCAN theo tư duy dựa trên mật độ (density) "những điểm tụ tập dày đặc thì gom lại". Khác biệt căn bản này quyết định điểm mạnh·yếu của hai thuật toán. K-means tìm tốt các cụm tỏa tròn quanh tâm nhưng yếu với cụm dạng dài hay hình lưỡi liềm và với điểm ngoại lai (outlier), còn DBSCAN phân biệt được cùng lúc cụm có hình dạng tùy ý và điểm ngoại lai. Rốt cuộc, kỹ thuật nào đúng tùy thuộc hình dạng·quy mô·mục đích của dữ liệu, nên từ góc nhìn Kỹ sư chuyên nghiệp (Professional Engineer), con mắt phán đoán "khi nào dùng cái gì" là cốt lõi.

B. Bối cảnh ra đời và sự cần thiết

Bối cảnh nổi lên của kỹ thuật phân cụm và phân loại là sự bùng nổ dữ liệu. Dữ liệu khách hàng·giao dịch·log mà doanh nghiệp tích lũy quá đồ sộ để con người dò bằng mắt tìm quy tắc, và cũng khó lập trước giả thuyết phân tích. Khi đó, phân cụm không giám sát cung cấp cách tiếp cận khám phá (exploratory) "trước hết hãy xem dữ liệu tự chia thành những khối nào", còn phân loại có giám sát cung cấp cách tiếp cận dự đoán (predictive) "dựa vào đáp án đã biết để dự đoán lớp của dữ liệu mới". Ví dụ, khi nhà mạng chia hàng chục triệu thuê bao thành các phân khúc marketing thì không có đáp án nên dùng phân cụm, còn khi xác định giao dịch thẻ tín dụng là bình thường hay gian lận thì dùng phân loại đã học nhãn quá khứ.

2. K-means Clustering

Là kỹ thuật phân cụm dựa trên tâm (centroid-based), chia dữ liệu thành K cụm định trước và lặp lại việc cập nhật tâm sao cho tối thiểu hóa tổng bình phương khoảng cách (SSE, Sum of Squared Errors) giữa tâm (centroid) của mỗi cụm và dữ liệu thuộc về nó.

Hoạt động của K-means trực quan và được tóm tắt thành bốn bước lặp. Đầu tiên đặt ngẫu nhiên K tâm ban đầu (khởi tạo), gán mỗi dữ liệu cho tâm gần nhất (gán), tính lại tâm bằng tọa độ trung bình của các dữ liệu được gán (cập nhật), và lặp lại gán và cập nhật cho đến khi tâm không di chuyển nữa (hội tụ). Quá trình này làm SSE giảm đơn điệu nên chắc chắn hội tụ, nhưng không có bảo đảm điểm hội tụ đó là tối ưu toàn cục — đây là giới hạn cốt lõi.

Điểm yếu lớn nhất của K-means là phụ thuộc vào tâm ban đầu và phải chỉ định trước K. Nếu chọn sai tâm ban đầu thì bị mắc kẹt ở tối ưu cục bộ (local optimum) và cho ra cụm sai lệch, và nhà phân tích cũng phải quyết định trước K bằng bao nhiêu. Để giảm nhẹ điều này, kỹ thuật khởi tạo K-means++ trải các tâm ban đầu xa nhau được dùng rộng rãi, và ngày nay các thư viện chính như scikit-learn lấy nó làm mặc định. Các kỹ thuật thực tiễn tìm K phù hợp tiêu biểu gồm phương pháp khuỷu tay (Elbow) tăng dần K để tìm điểm mà mức giảm SSE gãy khúc, và hệ số Silhouette xem xét cùng lúc độ kết dính và độ tách biệt của cụm.

K-means có độ phức tạp tính toán nhẹ O(n·K·số lần lặp) và dễ mở rộng cho dữ liệu lớn, nên là thuật toán phân cụm được thử đầu tiên trong thực tế. Ví dụ điển hình là chiến dịch thương mại điện tử chia khách hàng theo ba trục tần suất·giá trị·độ gần đây mua hàng (RFM) thành 5 phân khúc (K=5) để phân biệt khách hàng tốt và khách hàng có nguy cơ rời bỏ. Tuy nhiên, K-means ngầm giả định mỗi cụm có dạng cầu (spherical) và kích thước tương tự, nên với cụm dạng dài, cụm có mật độ khác biệt lớn, hay dữ liệu lẫn ngoại lai, tâm bị méo và hiệu năng giảm. Ngoài ra, vì nhạy cảm với thang đo khoảng cách nên chuẩn hóa thang đo đặc trưng (standardization) gần như là bắt buộc.

Nhìn bằng con số sẽ hiểu rõ hơn. Ví dụ, nếu dùng chung trục giá trị mua hàng tháng ở mức hàng triệu won với trục số lần mua ở mức một chữ số mà không chuẩn hóa, khoảng cách Euclid trên thực tế chỉ phản ánh mỗi trục giá trị mua hàng và bỏ qua thông tin số lần. Vì vậy, chỉ sau khi chuẩn hóa hai trục về trung bình 0·độ lệch chuẩn 1 thì hai đặc trưng mới đóng góp cân bằng vào phân cụm. Ngoài ra, khi thay K thành 3·4·5·6 và vẽ SSE, thường xuất hiện 'khuỷu tay' tại một K cụ thể nơi mức giảm đột ngột trở nên thoai thoải; quy trình thực tiễn là lấy điểm này làm ứng viên K phù hợp và kiểm tra chéo bằng hệ số Silhouette (thường từ 0.5 trở lên là tốt).

3. DBSCAN

Là kỹ thuật phân cụm dựa trên mật độ, hình thành cụm dựa trên mật độ (số điểm lân cận tồn tại trong một bán kính nhất định), mở rộng vùng mật độ cao thành một cụm và tách các điểm mật độ thấp không thuộc về đâu thành nhiễu (ngoại lai). DBSCAN là viết tắt của Density-Based Spatial Clustering of Applications with Noise.

DBSCAN hoạt động với hai tham số, đó là bán kính ε (epsilon) quy định lân cận và số lân cận tối thiểu MinPts để trở thành điểm lõi. Nếu trong bán kính ε của một điểm có từ MinPts điểm trở lên thì điểm đó được xem là điểm lõi (core point), các lân cận của nó được hấp thụ vào cùng cụm, và cụm được mở rộng theo chuỗi. Điểm là lân cận của điểm lõi nhưng bản thân không phải điểm lõi là điểm biên (border point), còn điểm không phải lân cận của bất kỳ điểm lõi nào được phân loại là nhiễu (noise). Vì cụm cứ vươn ra chừng nào mật độ còn nối liền, nó tìm ra một cách tự nhiên cả cụm có hình dạng tùy ý như lưỡi liềm·xoắn ốc.

Điểm mạnh của DBSCAN được tóm tắt thành ba điều. Thứ nhất, không cần định trước K, số cụm được quyết định tự động từ dữ liệu. Thứ hai, lọc ngoại lai thành nhiễu mà không cần xử lý riêng, nên được dùng trực tiếp cho phát hiện bất thường (anomaly detection). Thứ ba, nắm bắt được hình dạng tùy ý không lồi. Trong thực tế, nó được dùng để tự động xác định khu thương mại tập trung cửa hàng dựa trên tọa độ GPS, hay phân đoạn vật thể và loại bỏ nhiễu trong đám mây điểm LiDAR. Ví dụ, gom vị trí đơn giao hàng bằng DBSCAN thì dù không biết K, các khu vực giao hàng dày đặc vẫn tự động hiện ra.

Ngược lại, điểm yếu của DBSCAN là nhạy cảm tham số và chênh lệch mật độ. Nếu chọn sai ε và MinPts thì các cụm dính thành một hoặc tất cả thành nhiễu, và nếu trong một tập dữ liệu có lẫn các cụm có mật độ khác biệt lớn thì khó bắt được tất cả bằng một ε duy nhất. Để giảm nhẹ vấn đề này, HDBSCAN (Hierarchical DBSCAN) phản ánh cấu trúc phân cấp mật độ đã được đề xuất và ngày càng được dùng nhiều trong thực tế. Ngoài ra, với dữ liệu nhiều chiều, 'lời nguyền số chiều' làm khái niệm khoảng cách bị pha loãng khiến hiệu dụng của cách tiếp cận dựa trên mật độ giảm.

Kỹ thuật thực tiễn để chọn giá trị ε được dùng rộng rãi là đồ thị k-khoảng cách (k-distance plot). Tính khoảng cách từ mỗi điểm đến lân cận gần thứ k rồi sắp xếp tăng dần, sẽ xuất hiện điểm 'đầu gối (knee)' nơi phần lớn các điểm tăng thoai thoải rồi vọt lên đột ngột ở vùng nhiễu, và khoảng cách tương ứng với đầu gối đó được lấy làm ứng viên ε. MinPts thường lấy điểm xuất phát khoảng gấp đôi số chiều dữ liệu (ví dụ: 2 chiều thì khoảng 4) rồi điều chỉnh. Như vậy, DBSCAN không phải định K nhưng trả một chi phí khác là tinh chỉnh ε·MinPts, và đổi lại có được năng lực mà K-means không làm được là tìm cụm hình dạng tùy ý và tách ngoại lai.

4. SVM (Support Vector Machine)

Là kỹ thuật phân loại có giám sát tìm siêu phẳng (hyperplane) tối ưu chia hai lớp, sao cho tối đa hóa lề (margin) — khoảng trống với các điểm dữ liệu gần ranh giới nhất (vector hỗ trợ) — để nâng cao hiệu năng tổng quát hóa.

Lý do SVM không chỉ tìm bất kỳ ranh giới nào chia hai lớp mà nhất định tìm ranh giới 'lề cực đại' là vì hiệu năng tổng quát hóa. Ranh giới càng cách xa dữ liệu huấn luyện, khoảng dư (lề) càng lớn, thì dữ liệu mới chưa thấy khi huấn luyện dù dao động một chút cũng không vượt qua ranh giới, giảm phân loại sai. Chính việc thứ quyết định ranh giới này không phải toàn bộ dữ liệu mà chỉ số ít điểm gần ranh giới nhất, tức vector hỗ trợ (support vector), là vẻ thanh lịch và nguồn gốc hiệu quả của SVM. Dữ liệu thực tế không tách biệt hoàn hảo, nên dùng lề mềm (soft margin) cho phép một ít phân loại sai và điều chỉnh mức độ đó bằng siêu tham số C. C lớn thì phạt nặng phân loại sai khiến lề hẹp lại, C nhỏ thì nới rộng lề nhưng khoan dung với phân loại sai.

Dữ liệu không thể chia tuyến tính được giải quyết bằng thủ thuật kernel (kernel trick). Ánh xạ dữ liệu rối rắm trong không gian gốc sang không gian đặc trưng nhiều chiều thì có thể tách bằng siêu phẳng tuyến tính, và điểm then chốt là đạt hiệu quả đó chỉ bằng hàm kernel (tích vô hướng) mà không thực sự tính tọa độ nhiều chiều. Tiêu biểu, kernel RBF (hàm cơ sở xuyên tâm) tạo ranh giới phi tuyến linh hoạt nên thường được dùng làm mặc định trong thực tế, ngoài ra còn dùng kernel đa thức·sigmoid. Tinh chỉnh đồng thời γ (gamma) quyết định độ rộng của RBF và C nói trên (grid search·kiểm định chéo) là cốt lõi của SVM trong thực tế.

SVM đặc biệt mạnh với dữ liệu nhiều chiều·quy mô nhỏ, nơi số đặc trưng nhiều hơn số mẫu. Nó từng cho hiệu năng mạnh trong thời gian dài ở các bài toán phân loại có ung thư hay không bằng dữ liệu biểu hiện gen (hàng nghìn gen so với vài trăm mẫu), hay phân chia văn bản thành spam/bình thường. Nó từng là một trong những bộ phân loại mạnh nhất thời kỳ trước học sâu, với ưu điểm là cơ sở lý thuyết (tối thiểu hóa rủi ro cấu trúc) vững chắc và tương đối bền vững trước quá khớp. Tuy nhiên, có các giới hạn: khi số mẫu lên đến hàng trăm nghìn trở lên thì chi phí huấn luyện tăng vọt, không trực tiếp cho đầu ra xác suất (cần hiệu chỉnh riêng), và tốn công tinh chỉnh kernel·C·γ.

SVM vốn là bộ phân loại nhị phân chia hai lớp, nên khi xử lý từ ba lớp trở lên thì kết hợp nhiều bộ phân loại nhị phân theo chiến lược một-với-phần-còn-lại (One-vs-Rest) hoặc một-với-một (One-vs-One). Ngoài ra còn có SVR (Support Vector Regression) mở rộng sang bài toán hồi quy, đổi khái niệm lề thành sai số cho phép (ε-tube) để dự đoán giá trị liên tục. Như vậy, chính xác hơn là hiểu SVM không phải một thuật toán đơn lẻ mà là một họ chia sẻ tư tưởng tối đa hóa lề, và độ tự do trong chọn kernel và tinh chỉnh siêu tham số vừa là tính linh hoạt vừa là gánh nặng vận hành.

5. So sánh

Khác biệt của ba kỹ thuật không đơn thuần là liệt kê hạng mục trong bảng mà tất yếu rẽ nhánh theo hai trục 'có hay không có đáp án và định nghĩa độ tương tự'. K-means và DBSCAN giống nhau ở chỗ không có đáp án, nhưng khác ở việc nhìn độ tương tự bằng khoảng cách hay mật độ, nên thể hiện xu hướng trái ngược về xử lý ngoại lai và hình dạng cụm. SVM học đáp án nên khác tầng với hai kỹ thuật trước, không tạo cụm mà vạch ranh giới của các lớp đã được định nghĩa. Do đó, ba câu hỏi "có biết số cụm không, có cần lọc ngoại lai không, có nhãn đáp án không" chính là cây quyết định để chọn kỹ thuật.

flowchart TB
  D["Khai phá dữ liệu (phát hiện mẫu)"] --> C["Phân cụm (không giám sát)"]
  D --> CL["Phân loại (có giám sát)"]
  C --> K["K-means (dựa trên tâm·khoảng cách)"]
  C --> DB["DBSCAN (dựa trên mật độ)"]
  CL --> S["SVM (siêu phẳng lề cực đại)"]
  K --> K1["Mạnh với cụm dạng cầu·quy mô lớn"]
  DB --> D1["Hình dạng tùy ý·tách ngoại lai"]
  S --> S1["Nhiều chiều·xử lý phi tuyến bằng kernel"]
  style D fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style C fill:#e6f4ea,stroke:#188038,stroke-width:1px
  style CL fill:#fce8e6,stroke:#c5221f,stroke-width:1px

Dưới đây là sơ đồ quy trình thể hiện cách ba kỹ thuật được chọn·áp dụng trong pipeline phân tích thực tế. Sau khi làm sạch·chuẩn hóa dữ liệu gốc, rẽ nhánh theo mục đích và việc có nhãn hay không, và kết quả nhất định phải được kiểm chứng bằng chỉ số định lượng.

flowchart LR
  A["Thu thập dữ liệu nguồn"] --> B["Tiền xử lý (thiếu dữ liệu·chuẩn hóa·giảm chiều)"]
  B --> Q{"Có nhãn đáp án không?"}
  Q -->|"Không"| G{"Biết số cụm không?"}
  Q -->|"Có"| H["Huấn luyện SVM (tinh chỉnh C·kernel·γ)"]
  G -->|"Biết"| E["K-means (chỉ định K)"]
  G -->|"Không biết·ngoại lai quan trọng"| F["DBSCAN (ε·MinPts)"]
  E --> V["Kiểm chứng (Silhouette·Elbow)"]
  F --> V
  H --> W["Kiểm chứng (độ chính xác·F1·kiểm định chéo)"]
  V --> R["Diễn giải·Áp dụng nghiệp vụ"]
  W --> R
  style Q fill:#fef7e0,stroke:#f9ab00
  style G fill:#fef7e0,stroke:#f9ab00

6. Nâng cao: Ứng dụng thực tiễn và xu hướng mới nhất

Trong thực tế, ba kỹ thuật này ít khi được dùng đơn lẻ mà được kết hợp như một bước của pipeline. Luồng tiêu biểu là 'nắm cấu trúc dữ liệu trước bằng phân cụm không giám sát → dùng nhãn cụm thu được làm đặc trưng hoặc loại bỏ ngoại lai → xây dựng mô hình dự đoán bằng phân loại có giám sát'. Ví dụ, trong phát hiện giao dịch bất thường tài chính, dùng DBSCAN hay phát hiện bất thường dựa trên mật độ để lọc trước nhiễu rõ ràng, rồi huấn luyện bộ phân loại SVM·họ cây trên dữ liệu còn lại để nâng độ chính xác. Trong quản lý chất lượng sản xuất, chia log cảm biến thành các cụm mẫu vận hành bình thường bằng K-means, rồi cảnh báo các quan sát nằm xa mọi cụm như tín hiệu bất thường.

Cũng cần điểm qua các xu hướng phát triển kỹ thuật mới nhất. Thứ nhất, HDBSCAN bổ khuyết điểm yếu chênh lệch mật độ của DBSCAN đã được phổ biến qua thư viện (hdbscan, tích hợp sẵn trong scikit-learn 1.3+), đang trở thành phương pháp phân cụm mật độ ít nhạy cảm tham số. Thứ hai, với dữ liệu nhiều chiều·phi cấu trúc, thay vì phân cụm trực tiếp dữ liệu gốc, phân cụm sâu (deep clustering) học biểu diễn ít chiều bằng autoencoder·embedding rồi áp dụng K-means đã trở thành chuẩn. Thứ ba, SVM đã nhường chỗ cho học sâu·gradient boosting với dữ liệu siêu lớn, nhưng vẫn là lựa chọn hiệu quả trong các miền sinh học·văn bản có ít mẫu nhưng nhiều đặc trưng và trong môi trường nhúng nhẹ. Trong bài làm Kỹ sư chuyên nghiệp, giữ vững quan điểm "không có thuật toán vạn năng (No Free Lunch), bản chất là chọn kỹ thuật phù hợp đặc tính dữ liệu và kiểm chứng" là hữu hiệu.

7. Các điểm cần lưu ý và hàm ý

1. Lựa chọn dựa trên đặc tính dữ liệu là ưu tiên hàng đầu. Nếu biết số cụm và cụm nhìn chung tròn thì K-means, nếu không biết số cụm hoặc cần hình dạng tùy ý·phát hiện ngoại lai thì DBSCAN, nếu có nhãn đáp án và là phân loại nhiều chiều với ranh giới rõ ràng thì SVM là phù hợp. Cần tiếp cận không phải bằng câu hỏi 'kỹ thuật nào tốt nhất' mà là 'giả định nào phù hợp với bài toán này'.

2. Tiền xử lý và chuẩn hóa quyết định hiệu năng. Cả ba kỹ thuật đều dựa trên khoảng cách·tích vô hướng, nên nếu thang đo đặc trưng khác nhau thì trục có giá trị lớn sẽ chi phối kết quả. Chuẩn hóa (z-score), giảm chiều (PCA), xử lý dữ liệu thiếu quan trọng không kém việc chọn thuật toán, đặc biệt với dữ liệu nhiều chiều thì chọn đặc trưng để giảm nhẹ lời nguyền số chiều là bắt buộc.

3. Kết quả nhất định phải được hậu thuẫn bằng kiểm chứng định lượng·định tính. Với phân cụm, xác nhận số cụm phù hợp bằng hệ số Silhouette·Elbow và kiểm chứng tính hợp lý bằng diễn giải của chuyên gia nghiệp vụ; với phân loại, không chỉ độ chính xác mà cả precision·recall·F1 và kiểm định chéo để đề phòng quá khớp. Không phụ thuộc vào một chỉ số hay một lần chạy duy nhất.

4. Bảo đảm tính vững chắc bằng ensemble và kết hợp. Thay vì phụ thuộc vào một kỹ thuật, dùng kết quả phân cụm làm đặc trưng đầu vào cho phân loại, hoặc kiểm tra chéo kết quả của nhiều thuật toán để nâng độ tin cậy. Pipeline kết hợp không giám sát (phát hiện cấu trúc) và có giám sát (dự đoán) là chuẩn mực trong thực tế.

5. Cân nhắc đánh đổi giữa khả năng diễn giải và chi phí vận hành. Quyết định kernel của SVM khó diễn giải, việc đặt K của K-means có thể tùy tiện, còn DBSCAN tốn chi phí tinh chỉnh tham số. Trong các miền chịu quy định·kiểm toán, cần đánh giá không chỉ độ chính xác mà cả khả năng giải thích và tái hiện khi chọn kỹ thuật.

Tài liệu tham khảo

• scikit-learn User Guide — Clustering (K-means·DBSCAN): https://scikit-learn.org/stable/modules/clustering.html
• scikit-learn User Guide — Support Vector Machines: https://scikit-learn.org/stable/modules/svm.html
• HDBSCAN documentation: https://hdbscan.readthedocs.io/

Tóm tắt một câu: K-means (dựa trên tâm·khoảng cách) và DBSCAN (dựa trên mật độ) là phân cụm không giám sát không có đáp án, SVM (siêu phẳng lề cực đại) là phân loại có giám sát học đáp án; cốt lõi là chọn phù hợp với hình dạng dữ liệu·số cụm·ngoại lai·việc có nhãn hay không và nâng tính vững chắc bằng tiền xử lý·kiểm chứng·ensemble.