Phân Cụm Phân Cấp: Tổng Quan Khái Niệm Kèm Ví Dụ

Bạn vừa được giao nhiệm vụ phân tích một bộ dữ liệu lớn và cần thực hiện phân tích cụm chuyên sâu. Bạn gặp thuật ngữ “phân cụm phân cấp” (hierarchical clustering), nhưng chính xác nó là gì và hoạt động như thế nào? 

Trong bài viết này, chúng ta sẽ khám phá khái niệm về phân cụm phân cấp và đưa ra các ví dụ thực tế để giúp bạn hiểu rõ hơn các ứng dụng của nó.

Phân cụm phân cấp là gì?

Phân cụm phân cấp là một thuật toán học không giám sát dùng để nhóm các điểm dữ liệu tương tự nhau thành các cụm. Thuật toán xây dựng một hệ phân cấp nhiều mức của các cụm bằng cách hoặc là gộp các cụm nhỏ thành cụm lớn hơn (kết tụ - agglomerative) hoặc chia một cụm lớn thành các cụm nhỏ hơn (phân chia - divisive). Kết quả là một cấu trúc dạng cây gọi là dendrogram.

Dendrogram là biểu diễn trực quan minh họa cách sắp xếp các cụm và mối quan hệ giữa chúng. Chiều cao của các nhánh trong dendrogram biểu thị khoảng cách hoặc độ không tương đồng tại thời điểm các cụm hợp nhất. Chiều cao thấp hơn cho biết các cụm được nối ở khoảng cách nhỏ hơn, tức là mức độ tương đồng cao hơn.

Vì sao phân cụm phân cấp quan trọng trong machine learning

Phân cụm phân cấp đặc biệt hữu ích khi số lượng cụm chưa được biết trước. Nó cho phép chuyên viên phân tích dữ liệu và nhà khoa học dữ liệu khám phá trực quan cấu trúc dữ liệu thông qua dendrogram. 

Kỹ thuật này cũng có khả năng phát hiện các cụm lồng nhau và được dùng rộng rãi trong các lĩnh vực như genomics, phân khúc khách hàng và tổ chức tài liệu.

Ví dụ, giả sử chúng ta có một bộ dữ liệu về lịch sử mua hàng của khách. Sử dụng phân cụm phân cấp, chúng ta có thể nhóm khách hàng có hành vi mua sắm tương tự vào các cụm và xác định các phân khúc thị trường tiềm năng cho chiến lược tiếp thị theo mục tiêu.

Phân cụm phân cấp và K-Means khác nhau thế nào

Khi thực hiện nhiệm vụ phân cụm, đa số thường cân nhắc giữa hai phương pháp chính: phân cụm phân cấp hoặc K-means.

Vậy chúng khác nhau ở điểm nào? Hãy xem các khác biệt dưới đây để có cái nhìn rõ hơn.

• K-Means:
• Cần xác định trước số cụm trước khi chạy.
• Hiệu quả và mở rộng tốt với bộ dữ liệu lớn.
• Giả định các cụm có dạng hình cầu và kích thước tương đương.
• Phân cụm phân cấp:
• Không cần số cụm định trước.
• Dễ diễn giải hơn nhờ dendrogram.
• Chậm hơn trên bộ dữ liệu lớn nhưng tốt hơn để khám phá cấu trúc.

Khi so sánh hai phương pháp, có một số khía cạnh khiến phân cụm phân cấp trở nên nổi bật.

Dưới đây là một số trường hợp phân cụm phân cấp phát huy hiệu quả:

• Linh hoạt trong việc chọn cụm bằng dendrogram.
• Phù hợp với bộ dữ liệu nhỏ hoặc khi cần phân cấp trực quan.
• Xử lý được các hình dạng cụm phức tạp.

Tuy nhiên, cũng có một vài hạn chế, chẳng hạn như:

• Tốn kém tính toán
• Nhạy với dữ liệu nhiễu và ngoại lai.

Bạn có thể hỏi: Khi nào nên dùng phân cụm phân cấp?

Phân cụm phân cấp là lựa chọn tuyệt vời trong các ứng dụng sau:

• Phân tích dữ liệu thăm dò
• Phân tích mẫu biểu hiện gene
• Phân khúc thị trường với bộ dữ liệu kích thước vừa

Các loại phân cụm phân cấp

Trong kỹ thuật phân cụm phân cấp, bạn sẽ gặp một số loại, mỗi loại cung cấp những góc nhìn và kết quả khác nhau. Hai loại chính là kết tụ (từ dưới lên - bottom-up) và phân chia (từ trên xuống - top-down).

Nguồn: Himanshu Sharma trên Medium

1. Kết tụ (Bottom-Up)

Phân cụm kết tụ bắt đầu với mỗi điểm dữ liệu là một cụm riêng lẻ và lặp lại việc gộp cặp cụm gần nhau nhất cho đến khi chỉ còn một cụm hoặc cho đến khi đạt điều kiện dừng (như số cụm mong muốn).

Phương pháp này còn gọi là từ dưới lên vì bắt đầu từ đáy (các điểm dữ liệu riêng lẻ) và xây dần lên đỉnh (cụm cuối cùng).

Hướng dẫn từng bước:

1. Xem mỗi điểm dữ liệu là một cụm đơn lẻ.
2. Tính khoảng cách từng cặp giữa tất cả các cụm.
3. Gộp hai cụm có khoảng cách nhỏ nhất.
4. Cập nhật ma trận khoảng cách để phản ánh tập cụm mới.
5. Lặp lại bước 2–4 cho đến khi tất cả điểm thuộc về một cụm duy nhất.

Phương pháp này được dùng rộng rãi nhờ tính đơn giản và dễ triển khai.

Dưới đây là ví dụ triển khai bằng Python:

import numpy as np
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
import matplotlib.pyplot as plt

# Samples data
data = np.array([[1, 2], [2, 3], [5, 8], [8, 8], [1, 0], [0, 1]])

# Applies agglomerative clustering using Ward's method
Z = linkage(data, method='ward')

# Plots dendrogram
plt.figure(figsize=(8, 4))
dendrogram(Z)
plt.title('Agglomerative Clustering Dendrogram')
plt.xlabel('Data Points')
plt.ylabel('Distance')
plt.show()

# Extracts clusters (e.g., form 2 clusters)
clusters = fcluster(Z, t=2, criterion='maxclust')
print("Cluster assignments:", clusters)Được hỗ trợ bởi

2. Phân chia (Top-Down)

Phân cụm phân chia bắt đầu với tất cả điểm dữ liệu trong một cụm duy nhất và đệ quy tách chúng thành các cụm nhỏ hơn. Quá trình tiếp tục cho đến khi mỗi điểm dữ liệu nằm trong một cụm riêng của nó.

Nó còn được gọi là phương pháp từ trên xuống, vì bắt đầu ở đỉnh (một cụm duy nhất) và tách dần thành các cụm nhỏ hơn.

Hướng dẫn từng bước:

1. Bắt đầu với một cụm lớn chứa tất cả điểm dữ liệu.
2. Tách cụm thành hai cụm khác biệt nhau nhất có thể.
3. Áp dụng lại quá trình tách một cách đệ quy lên từng cụm thu được.

Các phương pháp phân chia thường tốn kém tính toán hơn do tính đệ quy, và độ chính xác phụ thuộc nhiều vào chiến lược tách. Phương pháp kết tụ phổ biến hơn do dễ triển khai và được nhiều phần mềm hỗ trợ.

Lưu ý: Phân cụm phân cấp theo hướng phân chia không được hỗ trợ sẵn sàng trong các thư viện Python tiêu chuẩn như phân cụm kết tụ. Một cách tiếp cận là dùng các thuật toán phân cụm như k-means theo kiểu đệ quy.

Dưới đây là ý tưởng mã cho việc tách k-means đệ quy mô phỏng:

from sklearn.cluster import KMeans

def divisive_clustering(data, depth=2):
    if depth == 0 or len(data) <= 1:
        return [data]

    kmeans = KMeans(n_clusters=2, random_state=42).fit(data)
    labels = kmeans.labels_
    cluster1 = data[labels == 0]
    cluster2 = data[labels == 1]

    return divisive_clustering(cluster1, depth - 1) + divisive_clustering(cluster2, depth - 1)

# Run recursive splitting to simulate divisive clustering
split_clusters = divisive_clustering(data, depth=2)
for i, cluster in enumerate(split_clusters):
    print(f"Cluster {i+1} size: {len(cluster)}")Được hỗ trợ bởi

Đoạn mã đơn giản này minh họa cách tiếp cận khái niệm cho phân cụm phân chia bằng k-means đệ quy. Lưu ý rằng các phương pháp phân chia chuẩn như DIANA dùng tiêu chí tách khác.

Các khái niệm và thuật ngữ then chốt

Phân cụm phân cấp liên quan đến một số khái niệm và thuật ngữ quan trọng cần hiểu rõ. Để nắm bắt toàn bộ quy trình, chúng ta sẽ đi sâu hơn vào các khái niệm này bên dưới.

1. Dendrogram

Dendrogram là cấu trúc dạng cây trực quan hóa quá trình phân cụm phân cấp. Mỗi mức của cây biểu thị một thao tác gộp hoặc tách, và chiều cao của nhánh biểu thị khoảng cách (hoặc độ không tương đồng) tại thời điểm các cụm được nối lại.

Vì sao nó quan trọng:

• Cho phép quan sát trực quan các cụm ở các mức khác nhau.
• Bằng cách “cắt” dendrogram tại một độ cao nhất định, bạn có thể chọn số cụm phù hợp nhất với dữ liệu.

2. Tiêu chí liên kết (linkage)

Tiêu chí liên kết xác định cách tính khoảng cách giữa các cụm trong quá trình gộp.

Một số loại tiêu chí liên kết gồm:

Liên kết đơn (khoảng cách nhỏ nhất)

Tiêu chí này xét khoảng cách giữa các điểm gần nhất của hai cụm. Điều này có thể tạo ra các cụm dài, dạng chuỗi.

from scipy.spatial.distance import pdist, squareform
data = np.array([[1, 2], [2, 3], [5, 8]])
distance_matrix = squareform(pdist(data, metric='euclidean')) 
single_linkage_min = np.min(distance_matrix[0, 1:])
print("Single Linkage Distance between Cluster A (point 1) and Cluster B (point 2, 3):", single_linkage_min)Được hỗ trợ bởi

Liên kết đầy đủ (khoảng cách lớn nhất)

Tiêu chí này xét khoảng cách giữa các điểm xa nhất của hai cụm. Thường tạo ra các cụm chặt và có kích thước đồng đều.

single_linkage_max = np.max(distance_matrix[0, 1:])
print("Complete Linkage Distance between Cluster A and B:", single_linkage_max)Được hỗ trợ bởi

Liên kết trung bình (trung bình cộng)

Tiêu chí này xét khoảng cách trung bình giữa tất cả các điểm của một cụm với tất cả các điểm của cụm còn lại. Cung cấp sự cân bằng giữa liên kết đơn và liên kết đầy đủ.

average_linkage = np.mean(distance_matrix[0, 1:])
print("Average Linkage Distance between Cluster A and B:", average_linkage)Được hỗ trợ bởi

Các ví dụ đơn giản này minh họa cách khoảng cách được tính ban đầu. Tuy nhiên, trong quá trình phân cụm, các tiêu chí này (liên kết đơn, đầy đủ, trung bình) được áp dụng lặp lại giữa toàn bộ các cụm, không chỉ giữa các điểm riêng lẻ.

Phương pháp Ward

Phương pháp Ward là biến thể của cách tiếp cận liên kết trung bình nhằm tối thiểu tổng bình phương sai biệt trong tất cả các cụm. Phương pháp này có xu hướng tạo ra các cụm đồng đều hơn so với các phương pháp khác, và thường cho các cụm tách biệt, gần dạng hình cầu.

from scipy.cluster.hierarchy import linkage
linkage_ward = linkage(data, method='ward')
print("Ward's Linkage Matrix:\n", linkage_ward)Được hỗ trợ bởi

Mỗi phương pháp có điểm mạnh riêng và nên được lựa chọn dựa trên dữ liệu và bài toán sử dụng.

3. Thước đo khoảng cách

Thước đo khoảng cách sử dụng có ảnh hưởng đáng kể đến kết quả phân cụm.

Khoảng cách Euclid

Khoảng cách Euclid là khoảng cách đường thẳng giữa hai điểm trong không gian đa chiều. Đây là thước đo được dùng phổ biến nhất, đặc biệt với dữ liệu phân bố theo hình học.

Khoảng cách Manhattan

Manhattan distance, còn gọi là khoảng cách taxicab hoặc L1, là tổng các sai khác tuyệt đối trên các chiều. Hữu ích cho dữ liệu dạng lưới như ô phố hoặc giao dịch tài chính.

Độ tương đồng cosine

Cosine similarity đo cosin của góc giữa hai vector khác 0. Thước đo này lý tưởng cho dữ liệu văn bản hoặc khi độ lớn không quan trọng (ví dụ: vector tần suất từ).

Triển khai phân cụm phân cấp trong Python

Trong phần này, chúng ta sẽ đi qua triển khai thực tiễn của phân cụm phân cấp kết tụ bằng Python. Chúng ta sẽ bao quát từ tiền xử lý dữ liệu đến trực quan hóa kết quả bằng dendrogram.

Thư viện

Bắt đầu bằng cách nhập các thư viện cần thiết:

import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as pltĐược hỗ trợ bởi

Những gì chúng ta đã nhập ở đoạn mã trên:

• numpy và pandas để xử lý dữ liệu
• scipy.cluster.hierarchy để phân cụm và tạo dendrogram
• sklearn.preprocessing.StandardScaler để chuẩn hóa đặc trưng
• matplotlib để trực quan hóa

Dữ liệu mẫu

Trước khi bắt đầu phân tích, hãy tạo một bộ dữ liệu đồ chơi gồm các điểm 2D và chuẩn hóa nó. Chuẩn hóa là rất quan trọng với các thuật toán dựa trên khoảng cách.

Đây là hình dung bộ dữ liệu mẫu của chúng ta.

data = np.array([[1, 2], [2, 3], [5, 8], [8, 8], [1, 0], [0, 1]])
scaler = StandardScaler()
data_scaled = scaler.fit_transform(data)Được hỗ trợ bởi

Đây là mảng dữ liệu sau khi đã được chuẩn hóa.

Tạo ma trận liên kết & dendrogram

Chúng ta áp dụng phương pháp Ward để tạo ma trận liên kết, chứa thông tin phân cụm phân cấp. Sau đó, vẽ dendrogram.

linkage_matrix = linkage(data_scaled, method='ward')
plt.figure(figsize=(8, 4))
dendrogram(linkage_matrix)
plt.title('Dendrogram')
plt.xlabel('Data Points')
plt.ylabel('Distance')
plt.show()Được hỗ trợ bởi

Trong đoạn mã trên, linkage xây dựng phân cấp cụm, còn dendrogram giúp trực quan hóa cách các cụm được hình thành.

Bằng cách quan sát nơi các đường dọc dài nhất trước khi hợp nhất, chúng ta có thể quyết định nơi “cắt” để tạo cụm. Hãy tìm đường dọc cao nhất không giao với bất kỳ cụm nào khác. Đó là nơi bạn nên cắt.

Trong trường hợp này, bạn sẽ cần cắt tại 2 cụm.

Tạo cụm

Tiếp theo, chúng ta cắt dendrogram để thu được số cụm cụ thể bằng fcluster:

clusters = fcluster(linkage_matrix, t=2, criterion='maxclust')
print(clusters)

plt.scatter(data_scaled[:, 0], data_scaled[:, 1], c=clusters, cmap='rainbow')
plt.title('Clusters')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()Được hỗ trợ bởi

Mỗi điểm dữ liệu sẽ được gán vào một trong hai cụm.

Một số thông tin bổ sung về đoạn mã:

• t=2: Chỉ định số cụm mong muốn.
• criterion='maxclust': Đảm bảo chúng ta nhận đúng t cụm.

Bạn có thể thay đổi t để thử nghiệm các số lượng cụm khác nhau.

Ví dụ thực tiễn: Phân khúc khách hàng

Phân cụm phân cấp thường được dùng trong phân khúc khách hàng. Hãy xem cách triển khai thực tiễn.

1. Tổng quan dữ liệu

Hãy mô phỏng một bộ dữ liệu đại diện cho khách hàng với hai đặc trưng: tuổi và thu nhập. Chúng ta sẽ dùng make_blobs để tạo dữ liệu tổng hợp này.

from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=100, centers=3, n_features=2, random_state=42)Được hỗ trợ bởi

2. Tiền xử lý

Tiếp theo, chúng ta cần chuẩn hóa các đặc trưng để đồng nhất thang đo và cải thiện độ chính xác phân cụm.

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)Được hỗ trợ bởi

Dữ liệu sau khi chuẩn hóa trông như sau:

3. Áp dụng phân cụm phân cấp

Khi dữ liệu đã được xử lý, chúng ta sẽ vẽ dendrogram để trực quan hóa cách các cụm hình thành.

linkage_matrix = linkage(X_scaled, method='ward')
plt.figure(figsize=(10, 5))
dendrogram(linkage_matrix)
plt.title('Customer Dendrogram')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()Được hỗ trợ bởi

4. Diễn giải kết quả

Từ dendrogram, chúng ta chọn một độ cao để “cắt” và tạo ra ba cụm:

labels = fcluster(linkage_matrix, t=3, criterion='maxclust')
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='rainbow')
plt.title('Customer Segments')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()Được hỗ trợ bởi

Hệ quả kinh doanh:

• Các cụm có thể đại diện cho nhóm khách hàng tiết kiệm, tầm trung và cao cấp.
• Cho phép cá nhân hóa tiếp thị và cải thiện chiến lược quan hệ khách hàng.

Ưu và nhược điểm của phân cụm phân cấp

Việc chọn phân cụm phân cấp cho phân tích của bạn có nhiều ưu điểm và hạn chế. 

Hãy xem một số điểm phổ biến dưới đây:

Ưu điểm

• Không cần chỉ định số cụm trước: Bạn có thể lựa chọn sau khi quan sát dendrogram.
• Trực quan dễ hiểu: Dendrogram giúp hiểu cách các cụm hình thành.
• Linh hoạt: Có thể xử lý nhiều hình dạng cụm tùy theo tiêu chí liên kết và thước đo khoảng cách.

Nhược điểm

• Tốn tài nguyên tính toán: Không lý tưởng cho bộ dữ liệu lớn.
• Nhạy với nhiễu và ngoại lai: Một vài điểm ngoại lai có thể làm méo đáng kể dendrogram.
• Không có tái gán: Khi đã gộp thì không thể hoàn tác, có thể dẫn đến phân cụm chưa tối ưu.

Kết luận

Phân cụm phân cấp là kỹ thuật phân cụm linh hoạt và dễ diễn giải, đặc biệt hữu ích trong phân tích dữ liệu thăm dò và các lĩnh vực như genomics và phân khúc khách hàng. Dù chi phí tính toán cao, điểm mạnh của nó nằm ở khả năng phát hiện các nhóm lồng nhau và tính linh hoạt trong việc chọn số cụm hậu kiểm thông qua trực quan hóa dendrogram.

Với các bộ dữ liệu nhỏ đến trung bình, nơi khả năng diễn giải là chìa khóa, phân cụm phân cấp vẫn là phương pháp ưa chuộng của cả nhà khoa học dữ liệu và chuyên viên phân tích.

Muốn tìm hiểu thêm về chi tiết của machine learning? Lộ trình Nền tảng Machine Learning với Python và bài hướng dẫn Giới thiệu về Phân cụm Phân cấp trong Python của chúng tôi là những điểm khởi đầu tuyệt vời.