Hướng dẫn implement dbscan from scratch - triển khai dbscan từ đầu

Tài nguyên quý giá nhất thế giới không còn là dầu, mà là dữ liệu

Nội dung chính Show

• Hiểu thuật toán
• Ưu điểm của DBSCAN
• Thực hiện
• Kết quả
• Dbscan vs k có nghĩa là
• Sự kết luận

Đáng ngạc nhiên như câu nói trên có thể nghe, nó hoàn toàn đúng. Bây giờ chúng ta đã chuyển sang một thế giới nơi dữ liệu là sức mạnh thực sự nhưng như chúng ta đã biết,

Với dữ liệu tuyệt vời, đến các vấn đề phân tích tuyệt vời.

Có lẽ không phải tất cả chúng ta nhưng các kỹ sư dữ liệu ngoài kia biết những gì & nbsp; tôi đang nói về. Nhiều lần chúng ta có những khối dữ liệu lan truyền ngẫu nhiên không có ý nghĩa gì từ cái nhìn đầu tiên. Đây là nơi phân cụm đến viện trợ của chúng tôi.

Trong các điều khoản đơn giản nhất, phân cụm đang tạo ra các nhóm trong dữ liệu của các điểm trông tương tự. Có nhiều thuật toán phân cụm đã được chứng minh rất hiệu quả,

• K có nghĩa là phân cụm
• K phân cụm trung bình
• Phân cụm DBSCAN & NBSP; & nbsp;

… đến tên một vài.

Đối với bài viết này, chúng tôi quên mất hai cái đầu tiên và tập trung vào phần cuối cùng là phân cụm DBSCAN.

DBSCAN là viết tắt của phân cụm không gian dựa trên mật độ của các ứng dụng có tiếng ồn.stands for Density-based spatial clustering of applications with noise.

Bài viết này sẽ bao gồm những điều sau đây;

• Hiểu thuật toán DBSCAN
• Ưu điểm thuật toán DBSCAN
• Thực hiện thuật toán DBSCAN
• Dbscan vs k có nghĩa là

Chúng ta hãy đi đến đó.

Lưu ý: Phần thưởng thú vị ở cuối

---

Hiểu thuật toán

Giả sử chúng tôi có một số điểm dữ liệu ngẫu nhiên.

Trực quan, không thể đưa ra những điểm nào nên được nhóm lại với nhau vì nhiều điểm có sự khác biệt rất nhỏ trong chúng.

Để bắt đầu thuật toán, chúng tôi chọn một điểm ngẫu nhiên.

Điểm đỏ sẽ là điểm được chọn của chúng tôi

Đã đến lúc giới thiệu 2 tham số chính cho phân cụm DBSCAN.

1. Epsilon

Đây là bán kính của vòng tròn mà chúng ta phải vẽ xung quanh trọng tâm điểm của chúng ta.

2. Số điểm tối thiểu Minimum number of points

Đây là số điểm mà chúng tôi muốn trong khu phố của điểm tập trung của chúng tôi (trong vòng tròn).

… Tiếp tục với thuật toán

Chúng tôi vẽ một vòng tròn bán kính ‘Epsilon‘ xung quanh điểm được chọn và kiểm tra khu phố.epsilon‘ around the chosen point and inspect the neighbourhood.

Bây giờ, hãy để giả sử rằng chúng tôi giữ tham số ‘điểm tối thiểu‘ là 3. Đây là cách nó sẽ quan trọng.minimum points‘ parameter to be 3. This is how it would matter.

Có rất ít quy tắc để tuân theo ở đây;

• Một điểm là một điểm cốt lõi, nếu các điểm lân cận của nó lớn hơn hoặc bằng các điểm tối thiểu chúng tôi đã chọn khi bắt đầu.‘core point’ if its neighbouring points are greater than or equal to the minimum points we chose at the start.
• Một điểm là một điểm biên giới, nếu các điểm lân cận của nó nhỏ hơn điểm tối thiểu chúng tôi chọn khi bắt đầu.‘border point’ if its neighbouring points are less than the minimum points we chose at the start.
• Một điểm được coi là ‘tiếng ồn nếu nó không có điểm trong khu phố của nóNoise‘ if it has no points in its neighbourhood

Vẽ một vòng tròn và kiểm tra khu phố

Theo các quy tắc của thuật toán, điểm này là một điểm cốt lõi vì nó có nhiều hàng xóm (5) hơn số chúng tôi quyết định (3).

Tất cả những điểm này được cho là một phần của một cụm duy nhất.

tập hợp lại với nhau

** Vì đó là một điểm cốt lõi, bây giờ chúng tôi chuyển sang áp dụng cùng một thuật toán trên tất cả các hàng xóm của nó. **

tìm thấy một điểm đi lạc khác

Kiểm tra khu phố của tất cả các hàng xóm mà chúng ta thấy rằng có một điểm nữa nằm trong khu phố nhưng không phải là một phần của cụm. Bây giờ nó trở thành một phần của cụm màu đỏ.

Điểm trong khu phố mà điểm mới này nằm cũng là một điểm cốt lõi.

Một điểm cốt lõi khác

Vì vậy, chúng tôi kiểm tra điểm mới này để tiếp tục cụm.

Một điểm biên giới được tìm thấy

Có vẻ như đây là một điểm biên giới, mặc dù nó trở thành một phần của cụm màu đỏ, chúng tôi sẽ không kiểm tra khu phố của nó để tiếp tục cụm.not check its neighbourhood to continue the cluster.

Có vẻ như chúng tôi đã tấn công một ngõ cụt; Không có thêm điểm để xem xét cho cụm này. Chà, điều này có nghĩa là chúng tôi bắt đầu thuật toán trên tất cả với các điểm mới, tạo ra một cụm mới.

Điểm mới

Điểm này có vẻ như là một ngõ cụt của riêng mình; Nó không có bất kỳ hàng xóm.

Điều tốt là chúng tôi xác định các quy tắc cho mọi tình huống. Điểm này là những gì chúng tôi dán nhãn là ‘tiếng ồn‘Noise‘

Tiếng ồn tìm thấy

Có vẻ như chúng ta phải bắt đầu lại.

Tiếp tục quá trình

Theo thuật toán, chúng tôi áp dụng các quy tắc đã đặt cho tất cả các điểm không được biết đến cho đến khi chúng tôi có tất cả trong một cụm.

Ưu điểm của DBSCAN

• Học tập không giám sát

Thuật toán DBSCAN yêu cầu không có nhãn để tạo các cụm do đó nó có thể được áp dụng cho tất cả các loại dữ liệu.

• Tự hình thành cụm

Không giống như đối tác nổi tiếng hơn nhiều của nó, K có nghĩa là, DBSCAN không yêu cầu một số cụm được xác định trước. Nó tạo thành các cụm bằng cách sử dụng các quy tắc chúng tôi xác định ở trên.

• Phát hiện tiếng ồn

Như đã chứng minh ở trên, nó không bị ảnh hưởng bởi các điểm ồn ào và có thể phát hiện và cô lập bất kỳ ngoại lệ nào trong dữ liệu.

---

Thực hiện

Mã đầy đủ có sẵn ở đây.

Chúng tôi bắt đầu bằng cách nhập tất cả các thư viện hữu ích.

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
import random
Code language: JavaScript (javascript)

Bây giờ chúng tôi rõ ràng cần một số dữ liệu mà chúng tôi có thể phân cụm.

centers = [(0, 4), (5, 5) , (8,2)]
cluster_std = [1.2, 1, 1.1]

X, y= make_blobs(n_samples=200, cluster_std=cluster_std, centers=centers, n_features=2, random_state=1)

plt.scatter(X[y == 0, 0], X[y == 0, 1], s=10, label="Cluster1")
plt.scatter(X[y == 1, 0], X[y == 1, 1], s=10, label="Cluster2")
plt.scatter(X[y == 2, 0], X[y == 2, 1], s=10, label="Cluster3")
plt.title("Scattered data")
Code language: JavaScript (javascript)

Dữ liệu được tạo tổng hợp

** Lưu ý: Các điểm dữ liệu có màu khác nhau biểu thị 3 phân phối khác nhau mà dữ liệu được rút ra từ **

Dữ liệu mà thuật toán của chúng tôi sẽ hoạt động sẽ trông như thế này;

Tất cả đều giống nhau

Hãy để xác định hai chức năng chính của chúng tôi;

def check_core_point(eps,minPts, df, index):
    #get points from given index
    x, y = df.iloc[index]['X']  ,  df.iloc[index]['Y']
    
    #check available points within radius
    temp =  df[((np.abs(x - df['X']) <= eps) & (np.abs(y - df['Y']) <= eps)) & (df.index != index)]
    
    #check how many points are present within radius
    if len(temp) >= minPts:
        #return format (dataframe, is_core, is_border, is_noise)
        return (temp.index , True, False, False)
    
    elif (len(temp) < minPts) and len(temp) > 0:
        #return format (dataframe, is_core, is_border, is_noise)
        return (temp.index , False, True, False)
    
    elif len(temp) == 0:
        #return format (dataframe, is_core, is_border, is_noise)
        return (temp.index , False, False, True)
Code language: PHP (php)

Hàm trên sẽ xem xét từng điểm trong tiêu điểm và xác định xem đó là điểm cốt lõi, điểm biên giới hay nhiễu.

def cluster_with_stack(eps, minPts, df):
    
    #initiating cluster number
    C = 1
    #initiating stacks to maintain
    current_stack = set()
    unvisited = list(df.index)
    clusters = []
    
    
    while (len(unvisited) != 0): #run until all points have been visited

        #identifier for first point of a cluster
        first_point = True
        
        #choose a random unvisited point
        current_stack.add(random.choice(unvisited))
        
        while len(current_stack) != 0: #run until a cluster is complete
            
            #pop current point from stack
            curr_idx = current_stack.pop()
            
            #check if point is core, neighbour or border
            neigh_indexes, iscore, isborder, isnoise = check_core_point(eps, minPts, df, curr_idx)
            
            #dealing with an edge case
            if (isborder & first_point):
                #for first border point, we label it aand its neighbours as noise 
                clusters.append((curr_idx, 0))
                clusters.extend(list(zip(neigh_indexes,[0 for _ in range(len(neigh_indexes))])))
                
                #label as visited
                unvisited.remove(curr_idx)
                unvisited = [e for e in unvisited if e not in neigh_indexes]
    
                continue
                
            unvisited.remove(curr_idx) #remove point from unvisited list
            
            
            neigh_indexes = set(neigh_indexes) & set(unvisited) #look at only unvisited points
            
            if iscore: #if current point is a core
                first_point = False
                
                clusters.append((curr_idx,C)) #assign to a cluster
                current_stack.update(neigh_indexes) #add neighbours to a stack

            elif isborder: #if current point is a border point
                clusters.append((curr_idx,C))
                
                continue

            elif isnoise: #if current point is noise
                clusters.append((curr_idx, 0))
                
                continue
                
        if not first_point:
            #increment cluster number
            C+=1
        
    return clusters
Code language: PHP (php)

Đây là chức năng chính của chúng tôi nơi toàn bộ logic thuật toán của chúng tôi nằm.

Trước khi chạy mã này, có một điều quan trọng cần xem xét khi mã hóa thuật toán. Có một trường hợp cạnh cụ thể có thể khiến thuật toán chạy mãi mãi hoặc gây ra vấn đề trong phân cụm. & nbsp;

Bất cứ khi nào chọn ra một điểm, có thể điểm đầu tiên bạn chọn ra có thể hóa ra là điểm biên giới. Bây giờ ở đây chúng ta có 3 khả năng;

1. Bỏ qua điểm và bắt đầu thuật toán một lần nữa với một điểm ngẫu nhiên khác.
2. Tạo một cụm riêng biệt của điểm này và hàng xóm của nó.
3. Dán nhãn điểm là nhiễu và di chuyển với thuật toán.

Tùy chọn đầu tiên ở trên có vẻ hợp lý nhưng chúng ta có thể gặp phải một ngõ cụt. Phân phối dữ liệu của bạn có thể sao cho cuối cùng bạn còn lại một số điểm như vậy chỉ tạo thành các cụm nhỏ. Thuật toán của bạn sẽ chỉ đơn giản là tiếp tục bỏ qua những điểm này và chạy mãi mãi.

Tùy chọn thứ hai có vẻ tốt quá nhưng các cụm nhỏ như vậy không có ý nghĩa trong dữ liệu và có vẻ vô dụng.

Tôi đã đi với tùy chọn thứ ba để giữ cho phân cụm càng sạch càng tốt,

#dealing with an edge case
            if (isborder & first_point):
                #for first border point, we label it aand its neighbours as noise 
                clusters.append((curr_idx, 0))
                clusters.extend(list(zip(neigh_indexes,[0 for _ in range(len(neigh_indexes))])))
                
                #label as visited
                unvisited.remove(curr_idx)
                unvisited = [e for e in unvisited if e not in neigh_indexes]
    
                continue
Code language: PHP (php)

Đoạn trích này là từ chức năng chính ở trên và liên quan đến trường hợp cạnh này.

Kết quả

Bây giờ chúng tôi chạy thuật toán và kiểm tra kết quả.

#radius of the circle defined as 0.6
eps = 0.6
#minimum neighbouring points set to 3
minPts = 3

data = pd.DataFrame(X, columns = ["X", "Y"] )
clustered = cluster_with_stack(eps, minPts, data)

idx , cluster = list(zip(*clustered))
cluster_df = pd.DataFrame(clustered, columns = ["idx", "cluster"])

plt.figure(figsize=(10,7))
for clust in np.unique(cluster):
    plt.scatter(X[cluster_df["idx"][cluster_df["cluster"] == clust].values, 0], X[cluster_df["idx"][cluster_df["cluster"] == clust].values, 1], s=10, label=f"Cluster{clust}")

plt.legend([f"Cluster {clust}" for clust in np.unique(cluster)], loc ="lower right")
plt.title('Clustered Data')
plt.xlabel('X')
plt.ylabel('Y')
Code language: PHP (php)

Phân cụm bằng DBSCAN

Có vẻ như chúng tôi có các cụm hợp lý. Nếu bạn cảm thấy như một số dữ liệu đã bị kết nối sai thì bạn có thể chơi xung quanh với giá trị Epsilon và Min-Points.

Dưới đây là một số kết quả từ việc thay đổi các giá trị này.

EPS = 0,5 - minpts = 3

EPS = 0,55 - minpts = 3

EPS = 0,58 - minpts = 4

---

Dbscan vs k có nghĩa là

K có nghĩa là, mặc dù phổ biến hơn nhiều, nhưng thiếu đằng sau DBSCAN trong một số trường hợp. Đầu tiên, nó cần một số được xác định trước cho bao nhiêu cụm chúng ta cần. Chúng tôi có thể không phải lúc nào cũng có thông tin này và có thể khá khó phân tích dữ liệu.

K có nghĩa là cũng không xác định các ngoại lệ và cố gắng nhóm mọi điểm trong một cụm.

from sklearn.cluster import KMeans

clustering = KMeans(3).fit(X)

plt.figure(figsize=(10,7))
for clust in np.unique(clustering.labels_):
    plt.scatter(X[clustering.labels_ == clust, 0], X[clustering.labels_ == clust, 1], s=10, label=f"Cluster{clust}")

plt.legend([f"Cluster {clust}" for clust in np.unique(clustering.labels_)], loc ="lower right")
Code language: JavaScript (javascript)

Chúng tôi sẽ áp dụng K có nghĩa là phân cụm từ thư viện Sklearn vào cùng một dữ liệu.

Có nghĩa là K với 3 cụm

3 cụm dường như được hình thành ổn nhưng chúng tôi có nhiều ngoại lệ không nên ở trong bất kỳ cụm nào.

Có một số trường hợp trong đó k có nghĩa là vs dbscan, dbscan lấy bánh. Các minh họa dưới đây giải thích điều này một cách hoàn hảo.

Nội dung tiền thưởng

Để có một hình ảnh thú vị của phân cụm DBSCAN, hãy truy cập liên kết sau.

Sự kết luận

DBSCAN có thể không phải là thuật toán phân cụm được biết đến rộng rãi nhất nhưng nó chắc chắn có lợi ích của nó. Hình minh họa ở trên cho thấy cách K có nghĩa là có thể tạo ra các cụm thực sự có thể không có ý nghĩa trong khi DBSCAN tìm thấy các mẫu phù hợp. Quyết định cuối cùng phụ thuộc vào loại dữ liệu của bạn và điều này sẽ có lợi cho bạn nhiều hơn.