Phân cụm theo thứ bậc là một trong những thuật toán học tập không giám sát phổ biến. Phân cụm theo thứ bậc lấy tên từ từ phân cấp, từ này có nghĩa là xếp hạng mọi thứ theo tầm quan trọng của chúng
Đây là những gì phân cụm theo thứ bậc thực hiện. Nó tìm các phần tử của tập dữ liệu có các thuộc tính tương tự đang được xem xét và nhóm chúng lại với nhau trong một cụm
Cuối cùng, chúng tôi thu được một cụm lớn duy nhất có các thành phần chính là cụm các điểm dữ liệu hoặc cụm của các cụm khác. Phân cụm theo thứ bậc tiếp cận vấn đề phân cụm theo hai cách. Hãy xem xét hai cách tiếp cận phân cụm theo thứ bậc này
điều kiện tiên quyết
Để làm theo, bạn cần phải có
- Trăn 3. 6 trở lên được cài đặt trên máy tính của bạn
- Kiến thức về ngôn ngữ lập trình Python
Các loại phân cụm phân cấp
phân cụm kết tụ
Trong phương pháp phân cụm này, chúng tôi bắt đầu với lá cụm và sau đó di chuyển lên trên cho đến khi thu được gốc cụm. Ban đầu, cách tiếp cận này giả định mỗi điểm dữ liệu trong tập dữ liệu là một cụm độc lập
Ban đầu, mỗi điểm dữ liệu được coi là một cụm đơn phần tử [lá]. Vì hai cụm tương tự nhất được kết hợp ở mỗi bước, chúng tôi thu được ít cụm hơn ở mỗi lần lặp hiện tại so với lần lặp trước đó
Quá trình này tiếp tục cho đến khi chúng tôi có được một cụm lớn [gốc] có các phần tử là các cụm thuộc tính có thể so sánh được. Sau khi hoàn tất tất cả quá trình phân cụm, chúng tôi trực quan hóa các cụm dữ liệu bằng cách sử dụng biểu đồ phân tán
Chúng ta có thể nâng cao hơn nữa sự hiểu biết của mình về thuật toán này bằng cách xem xét sơ đồ bên dưới
Nguồn. Trình hiển thị
Trong sơ đồ này, chúng tôi đã giả sử một tập dữ liệu có N phần tử trong đó N = 6. Dưới đây là các bước liên quan đến việc phân cụm ở trên
- Bước 1. Ban đầu, giả sử mỗi điểm dữ liệu là một cụm độc lập, tôi. e. 6 cụm
- Bước 2. Vào một cụm duy nhất, hợp nhất hai điểm dữ liệu gần nhất. Bằng cách làm như vậy, chúng tôi đã kết thúc với 5 cụm
- Bước 3. Một lần nữa, hợp nhất hai cụm gần nhất thành một cụm duy nhất. Bằng cách làm như vậy, chúng tôi đã kết thúc với 4 cụm
- Bước 4. Lặp lại bước ba ở trên cho đến khi thu được một cụm duy nhất của tất cả các điểm dữ liệu
Nếu chúng ta hình dung ra chương trình dendro, chúng ta sẽ có được cấu trúc giống như cái cây với gốc ở trên cùng giống như hình minh họa bên dưới
Nói chung, đây là thuật toán phân cụm kết tụ
phân cụm chia
Phân cụm chia rẽ là một cách tiếp cận từ trên xuống. Nói cách khác, chúng ta có thể thoải mái nói rằng đó là một trật tự đảo ngược của cụm kết tụ. Khi bắt đầu phân cụm, tất cả các điểm dữ liệu được coi là đồng nhất và do đó, nó bắt đầu với một cụm lớn gồm tất cả các điểm dữ liệu
Sau đó, tại mỗi lần lặp phân cụm, nhóm không đồng nhất nhất được chia thành hai cụm khác nhau sao cho phương sai trong chúng giảm đi. Quá trình tiếp tục cho đến khi đạt được tất cả số lượng cụm tối ưu
Tuy nhiên, trong thế giới thực, giả định ban đầu của phân cụm Chia rẽ, dữ liệu đồng nhất, có ít trọng số hơn so với giả định phân cụm Tích hợp rằng tất cả các điểm dữ liệu đều khác nhau. Điều này làm cho thuật toán này ít được sử dụng hơn trong các tác vụ phân cụm so với phân cụm tổng hợp
Như đã nói, bài viết này sẽ tập trung chú ý vào phân cụm kết tụ vì đây là thuật toán mà chúng tôi có nhiều khả năng áp dụng nhất trong các tác vụ phân cụm trong tương lai
Thuật toán phân cụm tổng hợp của chúng tôi đã nói về $hai\ gần nhất\ cụm$. Vì vậy, làm thế nào để chúng ta xác định làm thế nào các cụm lông từ nhau?
Trong học máy, có nhiều thước đo khoảng cách khác nhau mà chúng ta có thể sử dụng và đo khoảng cách giữa các điểm khác nhau
Các chỉ số này bao gồm
- khoảng cách Euclide
- khoảng cách Minkowski
- Khoảng cách hamming
- khoảng cách Manhattan
Khoảng cách Euclide đã cho thấy phạm vi sử dụng rộng rãi trong phép đo khoảng cách so với các phép đo khác. Chỉ số này được tính như
Vì chúng tôi biết các số liệu, chúng tôi có thể sử dụng và đo khoảng cách giữa các điểm cố định
Bây giờ là lúc quay lại và trả lời câu hỏi của chúng ta;
Khi chúng ta nói về các cụm, chúng ta đề cập đến một nhóm các điểm. Để đo khoảng cách giữa các nhóm điểm này, chúng ta cần phát triển một cách tiếp cận được xác định rõ ràng để nâng cao tính nhất quán trong nhiệm vụ phân cụm của chúng ta
Khoảng cách giữa hai cụm có thể được thực hiện theo năm cách tiếp cận khác nhau. Những cách tiếp cận này thường được gọi là phương pháp liên kết
Hãy để chúng tôi xem xét chúng và cố gắng hiểu cách chúng hoạt động
- liên kết đơn. Phương pháp này tính toán sự khác biệt giữa tất cả các cặp phần tử trong hai cụm. Sự khác biệt tối thiểu là khoảng cách giữa hai cụm. Điều này được minh họa trong hình bên dưới
- liên kết hoàn chỉnh. Phương pháp này tính toán sự khác biệt giữa tất cả các cặp phần tử trong hai cụm. Sự không giống nhau tối đa là khoảng cách giữa hai cụm. Điều này được minh họa trong hình bên dưới
- Liên kết trung bình. Phương pháp này tính toán khoảng cách giữa hai cụm bằng cách tìm tất cả các điểm khác biệt có thể có giữa hai cụm. Tất cả những khác biệt sau đó được tính trung bình và giá trị trung bình sau đó được lấy làm khoảng cách giữa các cụm này
- liên kết trọng tâm. Phương pháp này liên quan đến việc định tâm từng cụm và sau đó đo khoảng cách giữa các tâm thu được của hai cụm
- Phương pháp phương sai tối thiểu của Ward. Khoảng cách phường là một trong những thước đo tốt hơn để xác định khoảng cách giữa các cụm. Phương pháp này tìm kiếm độ lệch tổng hợp. Chẳng hạn, nếu chúng ta có hai cụm, chúng ta có thể giả vờ hợp nhất chúng thành một cụm và sau đó ước tính trọng tâm của cụm kết quả. Sau đó, chúng tôi tìm tổng độ lệch bình phương cho tất cả các điểm từ trọng tâm mới. Đối với các hợp nhất khác nhau, chúng tôi sẽ thu được các biến thể khác. Do đó, chúng tôi chọn khoảng cách với sự hợp nhất tối thiểu làm khoảng cách của chúng tôi
Triển khai phân cụm theo cấp bậc
Bây giờ là lúc để đưa tất cả những gì chúng ta đã thảo luận ở trên vào hành động. Ở đây, chúng ta sẽ sử dụng bộ dữ liệu trong thế giới thực để triển khai mô hình phân cụm kết tụ và cuối cùng hình dung cách mô hình có thể khám phá các cụm khác nhau từ dữ liệu
Như đã nói, bạn có thể tải xuống tập dữ liệu này và bắt đầu như bên dưới
Khi chúng tôi đã tải xuống dữ liệu của mình, điều đầu tiên là nhập tất cả các thư viện cần thiết cho phiên này. Đoạn mã sau nhập các thư viện này
Nhập các thư viện cần thiết
import numpy as np # to handle numeric data
import matplotlib.pyplot as plt # for visualization
import pandas as pd # for handling dataframe
Đọc tập dữ liệu vào không gian làm việc
Bây giờ các thư viện của chúng ta đã được nhập, hãy để chúng ta đọc dữ liệu vào không gian làm việc CỦA CHÚNG TA và in năm hàng đầu tiên bằng cách sử dụng hàm head[]
ourData = pd.read_csv['Mall_Customers.csv'] # read the data
ourData.head[] # print the first five rows of our dataset
Chúng tôi sẽ triển khai mô hình phân cụm theo cấp bậc của mình trên các cột Annual Income [k$] và Spending Score[]1-100 bằng bộ dữ liệu này. Vì vậy, chúng tôi cần trích xuất hai tính năng này từ tập dữ liệu của mình. Đoạn mã dưới đây hoàn thành hoạt động này
newData = ourData.iloc[:, [3, 4]].values # extract the two features from our dataset
Hai tính năng của dữ liệu mới của chúng tôi gần như có cùng tỷ lệ. Do đó, chúng tôi không cần phải mở rộng quy mô dữ liệu. Tuy nhiên, điều này sẽ không luôn luôn như vậy
Chúng tôi sẽ làm việc với các tập dữ liệu có giá trị hoàn toàn ở một thang đo khác. Trong tình huống như vậy, chúng tôi phải chia tỷ lệ dữ liệu để các tính năng khác nhau có thể so sánh được; . Lý do là phân cụm theo thứ bậc, giống như nhiều thuật toán khác trong học máy, dựa trên khoảng cách [khoảng cách Euclide]
Trước khi cố gắng phân cụm dữ liệu của chúng tôi, chúng tôi cần biết có bao nhiêu cụm dữ liệu của chúng tôi có thể được phân cụm một cách tối ưu. Vì vậy, trước tiên hãy triển khai chương trình dendro trên tập dữ liệu của chúng tôi để có được kiến thức này
Xác định số lượng cụm tối ưu với dendrogram
Mã dưới đây sẽ xây dựng một dendrogram trên tập dữ liệu của chúng tôi
import scipy.cluster.hierarchy as sch # importing scipy.cluster.hierarchy for dendrogram
dendrogram = sch.dendrogram[sch.linkage[X, method = 'ward']] # finding the optimal number of clusters using dendrogram
plt.title['Dendrogram'] # title of the dendrogram
plt.xlabel['Customers'] # label of the x-axis
plt.ylabel['Euclidean distances'] # label of the y-axis
plt.show[] # show the dendrogram
đầu ra
Đoạn mã trên trả về một dendrogram, như hình bên dưới
Xem xét chương trình dendro ở trên, số lượng cụm tối ưu có thể được xác định như sau;
Trên đường dài nhất đó, thiết lập một ngưỡng. Số lượng cụm mà chúng tôi có thể phân cụm dữ liệu của mình một cách tối ưu bằng với số lượng khoảng cách euclide [đường thẳng đứng] mà ngưỡng đã thiết lập cắt ngang
Trong biểu đồ dendro chúng ta vừa thu được, đường thẳng đứng dài nhất không có đường ngang kéo dài cắt ngang nằm ở phần màu xanh lá cây. Dòng thứ ba nằm giữa khoảng cách euclide [110 - 250]. Lấy ngưỡng của chúng tôi là 150, số cụm tối ưu thu được là năm
Biết số lượng tối ưu mà dữ liệu của chúng tôi nên nhóm vào;
Đào tạo mô hình phân cụm phân cấp trên dữ liệu
from sklearn.cluster import AgglomerativeClustering # this line of code imports AgglomerativeClustering model from sk-learn
'''
we need to create an AgglomerativeClustering object, and in it, we pass the following parameters:
n_cluster= 5, the number of clusters our model should return
affinity=euclidean, specify metric to be used to calculate distances
linkage= ward to regulate how distance calculation will be carried out between different clusters.
'''
Agg_hc = AgglomerativeClustering[n_clusters = 5, affinity = 'euclidean', linkage = 'ward']
y_hc = Agg_hc.fit_predict[newData] # model fitting on the dataset
Đoạn mã trên đã đào tạo mô hình của chúng tôi và bây giờ chúng tôi có thể tiếp tục và hình dung cách dữ liệu được phân cụm. Để làm điều này, hãy chạy mã dưới đây
Trực quan hóa cụm
# plotting cluster 1
plt.scatter[newData[y_hc == 0, 0], newData[y_hc == 0, 1], s = 100, c = 'red', label = 'Cluster 1'] # plotting cluster 2
plt.scatter[newData[y_hc == 1, 0], newData[y_hc == 1, 1], s = 100, c = 'blue', label = 'Cluster 2'] # plotting cluster 3
plt.scatter[newData[y_hc == 2, 0], newData[y_hc == 2, 1], s = 100, c = 'green', label = 'Cluster 3'] # plotting cluster 4
plt.scatter[newData[y_hc == 3, 0], newData[y_hc == 3, 1], s = 100, c = 'cyan', label = 'Cluster 4'] # plotting cluster 5
plt.scatter[newData[y_hc == 4, 0], newData[y_hc == 4, 1], s = 100, c = 'magenta', label = 'Cluster 5']
# plot title addition
plt.title['Clusters of customers']
# labelling the x-axis
plt.xlabel['Annual Income [k$]']
# label of the y-axis
plt.ylabel['Spending Score [1-100]']
# printing the legend
plt.legend[]
# show the plot
plt.show[]
Chi tiết cuối cùng mà chúng ta cần biết về phân cụm theo cấp bậc là nó phức tạp về thời gian và không gian và do đó không phải là giải pháp phù hợp cho các vấn đề phân cụm với bộ dữ liệu lớn
Phần kết luận
Trong bài viết này, chúng tôi đã xem xét phân cụm theo thứ bậc và các loại của nó. Đầu tiên, chúng tôi đã tìm hiểu cách thức hoạt động của các loại phân cụm theo thứ bậc này và sau đó kết luận rằng loại phù hợp nhất là phân cụm kết tụ
Chúng tôi cũng đã xem xét các phương pháp khác nhau được sử dụng để đo khoảng cách giữa các điểm dữ liệu và tiêu chí hướng dẫn chúng tôi cách thực hiện các phép đo này [Phương pháp mực]
Cuối cùng, chúng tôi đã triển khai mô hình của mình và trong quá trình đó, chúng tôi đã học được cách thu được số lượng cụm tối ưu bằng cách sử dụng chương trình dendro