Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Phân cụm phân cấp 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 phân cấp thu được tên của nó từ phân cấp từ, 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 phân cấp làm. Nó tìm thấy các yếu tố của bộ dữ liệu với các thuộc tính tương tự đượ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 ta có được một cụm lớn duy nhất có các yếu tố chính là cụm điểm dữ liệu hoặc cụm của các cụm khác. Phân cụm phân cấp tiếp cận các vấn đề phân cụm theo hai cách. Hãy cùng nhìn vào hai cách tiếp cận của phân cụm phân cấp.

Điều kiện tiên quyết

Để theo dõi, bạn cần phải có:

  1. Python 3.6 trở lên được cài đặt trên máy tính của bạn.
  2. 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 cách tiếp cận 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 cuối cùng có được gốc. Ban đầu, phương pháp này giả định từng đ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 một 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 có đượ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 ta có được một cụm lớn (gốc) có các yếu tố là cụm thuộc tính tương đương. Khi tất cả các phân cụm được hoàn thành, chúng tôi trực quan hóa các cụm dữ liệu bằng cách sử dụng một biểu đồ phân tán.

Chúng ta có thể tăng cường hơn nữa sự hiểu biết của chúng ta về thuật toán này bằng cách xem xét sơ đồ dưới đây.

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Nguồn: DisplayR

Trong sơ đồ này, chúng tôi đã giả định một bộ dữ liệu với các phần tử N trong đó n = 6. Dưới đây là các bước liên quan đến 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ức là 6 cụm. Initially, assume each data point is an independent cluster, i.e. 6 clusters.
  • Bước 2: thành 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 đó, chúng tôi đã kết thúc với 5 cụm. Into a single cluster, merge the two closest data points. By so doing, we ended up with 5 clusters.
  • 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. Bằng cách đó, chúng tôi đã kết thúc với 4 cụm. Again, merge the two closest clusters into a single cluster. By so doing, we ended up with 4 clusters.
  • Bước 4: Lặp lại bước ba ở trên cho đến khi có được một cụm duy nhất của tất cả các điểm dữ liệu. Repeat step three above until a single cluster of all data points is obtained.

Nếu chúng ta hình dung ra dendrogram, chúng ta sẽ có được cấu trúc giống như cây với gốc ở trên cùng như hình dưới đây:

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Nói chung, đây là những gì thuật toán phân cụm kết tụ.

Chia rẽ phân cụm

Cụm phân chia 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 thứ tự ngược của phân 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 của 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 bị giảm. Quá trình tiếp tục cho đến khi tất cả số lượng cụm tối ưu đạt được.divided into two different clusters such that the variance in them is reduced. The process continues until all the optimal number of clusters is attained.

Tuy nhiên, trong thế giới thực, giả định ban đầu về phân cụm gây chia rẽ, dữ liệu là đồng nhất, giữ trọng lượng ít hơn so với giả định phân cụm kết tụ rằng tất cả các điểm dữ liệu khác nhau. Điều này làm cho thuật toán này ít được sử dụng trong các nhiệm vụ phân cụm hơn so với phân cụm kết tụ.

Như đã nói, bài viết này sẽ chú ý đến phân cụm kết tụ vì đây là thuật toán mà chúng tôi rất có thể áp dụng trong các nhiệm vụ phân cụm trong tương lai.

Thuật toán phân cụm kết tụ của chúng tôi đã nói về hai cụm \ gần nhất \. Vậy làm thế nào để chúng ta xác định các cụm lông như thế nào với nhau?

Trong học máy, có nhiều số liệu 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.

Những số liệu 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 một loạt các sử dụng trong đo khoảng cách so với các số liệu khác. Số liệu này được tính là:

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Vì chúng ta biết các số liệu chúng ta có thể sử dụng và đo khoảng cách giữa các điểm cố định.

Bây giờ, thời gian để quay lại và trả lời câu hỏi của chúng tôi; Làm thế nào để chúng ta thực hiện phép đo này giữa các cụm?

Khi chúng tôi nói về các cụm, chúng tôi đề cập đến một nhóm đ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õ để tăng cường 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. Các phương pháp này thường được gọi là phương pháp liên kết.Linkage methods.

Chúng ta hãy nhìn vào họ và cố gắng hiểu cách chúng hoạt động.

  1. 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à những gì đủ điều kiện là khoảng cách giữa hai cụm. Điều này được minh họa trong hình dưới đây. This method computes dissimilarities between all pairs of elements in the two clusters. The minimum dissimilarity is what qualifies to be the distance between the two clusters. This is illustrated in the figure below.

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

  1. 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ác biệt tối đa là những gì đủ điều kiện là khoảng cách giữa hai cụm. Điều này được minh họa trong hình dưới đây. This method computes dissimilarities between all pairs of elements in the two clusters. The maximum dissimilarity is what qualifies to be the distance between the two clusters. This is illustrated in the figure below.

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

  1. 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 thấy tất cả sự khác biệt có thể xảy ra giữa hai cụm. Tất cả sự 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. This method computes the distance between two clusters by finding all possible dissimilarities between the two clusters. All the dissimilarities are then averaged, and the average value is then taken as the distance between these clusters.
  2. Liên kết tâm: Phương pháp này liên quan đến việc tập trung từng cụm và sau đó đo khoảng cách giữa các trung tâm thu được của hai cụm. This method involves centering each cluster and then measuring the distance between the obtained centers of the two clusters.

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

  1. Phương pháp phương sai tối thiểu Ward Ward: Khoảng cách Ward là một trong những số liệu tốt hơn để đi xa 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 trung tâm của cụm kết quả. Sau đó, chúng tôi tìm thấy tổng độ lệch bình phương cho tất cả các điểm từ Centroid mới. Đối với các sự hợp nhất khác nhau, chúng ta sẽ có đượ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à khoảng cách của chúng tôi. Ward distance is one of the better metrics for taking distances between clusters. This method looks for the aggregate deviation. For instance, if we have two clusters, we can pretend to merge them into one cluster and then estimate the centroid of the resulting cluster. After that, we find the sum of the squared deviation for all points from the new centroid. For different merges, we shall obtain other variations. Therefore, we choose the distance with the minimum merge as our distance.

Thực hiện phân cụm phân cấp

Bây giờ là thời gian để đư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 để thực hiện mô hình phân cụm kết tụ và cuối cùng trực quan hóa 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 bộ dữ liệu này và bắt đầu như dưới đây:

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. Mã sau nhập các thư viện này.

Nhập 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 cho không gian làm việc

Bây giờ các thư viện của chúng tôi đã được nhập, chúng ta hãy đọc dữ liệu vào không gian làm việc của chúng tôi và in năm hàng đầu tiên bằng hàm head().

ourData = pd.read_csv('Mall_Customers.csv') # read the data
ourData.head() # print the first five rows of our dataset

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Chúng tôi sẽ triển khai mô hình phân cụm phân cấp của chúng tôi trên các cột Annual Income (k$)Spending Score()1-100 bằng cách sử dụ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ừ bộ dữ liệu của chúng tôi. Mã dưới đây thực hiện 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 NewData của chúng tôi gần như trên cùng một quy mô. Do đó, chúng tôi không cần mở rộng dữ liệu. Tuy nhiên, điều này sẽ không luôn luôn là trường hợp.

Chúng tôi sẽ làm việc với các bộ dữ liệu có giá trị hoàn toàn ở quy mô khác. Trong tình huống như vậy, chúng tôi phải mở rộng dữ liệu để các tính năng khác nhau có thể so sánh được; Nếu không, chúng ta sẽ kết thúc với một mô hình kém hơn. Lý do là phân cụm phân cấp, 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 để thực hiện một dendrogram trên bộ 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ã bên dưới sẽ xây dựng một dendrogram trên bộ 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

Mã trên trả về một dendrogram, như được hiển thị bên dưới:

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Xem xét dendrogram ở trên, số lượng cụm tối ưu có thể được xác định như sau; Theo giả thuyết, ngoại suy tất cả các đường ngang trên toàn bộ dendrogram và sau đó tìm thấy đường thẳng đứng dài nhất không vượt qua các đường giả thuyết đó.

Trên dòng dài nhất đó, thiết lập một ngưỡng. Số lượng cụm chúng ta có thể phân cụm tối ưu dữ liệu của chúng ta bằng số lượng khoảng cách Euclide (đường thẳng đứng) các ngưỡng được thiết lập cắt ngang.

Trong dendrogram mà chúng tôi vừa có được, đường thẳng đứng dài nhất không có đường ngang ngang mở rộng là ở phần màu xanh lá cây. Dòng thứ ba là giữa khoảng cách Euclidian (110 - 250). Lấy ngưỡng của chúng tôi là 150, số lượng cụm tối ưu thu được là năm.

Biết số tối ưu mà dữ liệu của chúng tôi nên cụm thành; Bây giờ chúng tôi có thể đào tạo mô hình phân cụm của chúng tôi để đạt được mục tiêu này.

Đà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

Mã trên được đà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à trực quan hóa cách dữ liệu được phân cụm. Để làm điều này, hãy chạy mã bên dưới:

Cụm thông qua thường hóa

# 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()

Hướng dẫn single linkage clustering python code - mã python phân cụm liên kết đơn

Chi tiết cuối cùng chúng ta cần biết về phân cụm phân cấp là thời gian và không gian phức tạp của nó và do đó không phải là một giải pháp phù hợp cho các vấn đề phân cụm với các bộ dữ liệu lớn.

Sự kết luận

Trong bài viết này, chúng tôi đã xem xét phân cụm phân cấp và các loại của nó. Đầu tiên, chúng tôi đã học được cách các loại phân cụm phân cấp này hoạt động 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 về 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 này, chúng tôi đã học được cách có được số lượng cụm tối ưu bằng cách sử dụng dendrogram.

Hy vọng bạn tìm thấy bài viết này hữu ích.

Mã hóa hạnh phúc!


Đóng góp đánh giá ngang hàng của: Odhiambo Paul