DBSCAN từ con trăn đầu

Phân cụm là một kỹ thuật học tập không giám sát giúp tìm các mẫu trong dữ liệu mà không được thông báo rõ ràng mẫu cần tìm

DBSCAN thực hiện điều này bằng cách đo khoảng cách giữa mỗi điểm với nhau và nếu đủ các điểm đủ gần nhau, thì DBSCAN sẽ phân loại nó thành một cụm mới

Như đã thấy ở trên, có hai cụm riêng biệt trong Dữ liệu thử nghiệm. KMeans, một kỹ thuật phân cụm phổ biến khác, không thể phân cụm chính xác dữ liệu này vì KMeans tạo ra một ranh giới có thể phân tách tuyến tính giữa các cụm khi k=2

Thay vào đó, DBSCAN xác định các cụm dựa trên hai tham số. Epsilon và Min_Points

• Epsilon - Khoảng cách tối đa mà một điểm có thể từ một điểm khác được coi là hàng xóm

• Min_Points — Số điểm cần thiết trong phạm vi epsilon để được coi là một cụm

Lợi ích của DBSCAN

Nó yêu cầu kiến ​​thức miền tối thiểu để xác định các tham số đầu vào

Các thuật toán phân cụm khác như KMeans yêu cầu người dùng biết có bao nhiêu cụm tồn tại trong dữ liệu

Thay vì yêu cầu phải tìm bao nhiêu cụm, DBSCAN yêu cầu người dùng nhập khoảng cách tối đa mà mỗi điểm dữ liệu có thể được coi là một phần của cụm và cần bao nhiêu điểm dữ liệu để tạo thành cụm

Nó phát hiện ra các cụm có hình dạng bất kỳ

Vì DBSCAN tạo các cụm dựa trên epsilon và số lượng lân cận mà mỗi điểm có, nên nó có thể tìm thấy các cụm có hình dạng bất kỳ. DBSCAN hoạt động tốt nhất khi các cụm có cùng mật độ (khoảng cách giữa các điểm). Khi có các cụm có mật độ khác nhau, điều này có thể khiến DBSCAN khó xác định các cụm

Dõi theo

Nhấp vào đây để mở Google Colab Notebook triển khai Scikit-Learns DBSCAN và DBSCAN2 từ đầu. Nếu bạn muốn tìm hiểu thêm về những gì đang diễn ra bên dưới mui xe thì hãy tiếp tục đọc

# Download the test package
pip install -i https://test.pypi.org/simple/ dbscan2==0.0.3

# Import it!
from dbscan2 import dbscan2

# If you would like to plot the results import the following
from sklearn.datasets import make_moons
import pandas as pd

Để hiểu và triển khai DBSCAN từ đầu, chúng ta sẽ cần biết cách DBSCAN phân cụm dữ liệu. Cùng với Epsilon và Điểm tối thiểu, có ba thuật ngữ cần thiết hơn để hiểu

• Tiếng ồn - Đây là một điểm không có đủ hàng xóm trong epsilon để trở thành một phần của cụm (bao gồm cả chính nó)

• Điểm biên giới — Đây là điểm có hàng xóm trong epsilon nhưng không đủ hàng xóm để trở thành điểm cốt lõi. Những điểm này tạo thành cạnh của cụm

• Điểm cốt lõi — Điểm có Điểm tối thiểu cần thiết trong epsilon (bao gồm cả chính nó). Các điểm này cùng với các điểm biên sẽ tạo thành một cụm

Chúng tôi sẽ triển khai DBSCAN bằng một Lớp và gọi nó là dbscan2. Nó sẽ có hai phương pháp chính. phù hợp và dự đoán

def __init__()

Lớp sẽ được khởi tạo với hai mảng tính năng được tiêu chuẩn hóa, epsilon và số điểm cần thiết để tạo cụm. Nó cũng sẽ được khởi tạo với nhãn cụm và nhãn nhiễu

class dbscan2():
    def __init__(self,df, epsilon=1, min_points=5):
        self.df = np.array(df)
        self.epsilon = epsilon
        self.min_points = min_points
        self.cluster_label = 0
        self.noise = 0

Chức năng trợ giúp

Chúng tôi sẽ sử dụng khoảng cách euclide để đo mỗi điểm cách nhau bao xa. Khoảng cách Euclide sẽ đo khoảng cách đường thẳng thông thường từ một cặp tọa độ này đến một cặp khác

def dist(self, point1, point2):
    """Euclid distance function"""
    x1 = point1[0]
    x2 = point2[0]
    y1 = point1[1]
    y2 = point2[1]
# create the points
    p1 = (x1 - x2)**2
    p2 = (y1 - y2)**2
    return np.sqrt(p1 + p2)

Hàm trợ giúp khác mà chúng ta cần sẽ được gọi là rangeQuery. Hàm này sẽ giúp chúng ta tìm ra mỗi điểm có bao nhiêu láng giềng nằm trong epsilon

def rangeQuery(self, x):
    """Query database against x and return all points that are <= 
    epsilon"""
neighbors = []
for y in range(len(self.df)):
        q = self.df[y, :2]
# If the distance is <= than epsilon then append to neighbors list
        if self.dist(x, q) <= self.epsilon:
            neighbors.append(y)
return neighbors

def fit()

Hàm phù hợp của chúng tôi sẽ lặp qua toàn bộ tập dữ liệu và xác định có bao nhiêu điểm lân cận mà mỗi điểm trong tập dữ liệu của chúng tôi có

Nếu một điểm không có đủ hàng xóm (hàng xóm < min_points), thì nó sẽ được gắn nhãn là nhiễu

Nếu một điểm có đủ hàng xóm (hàng xóm ≥ min_points) thì điểm đó sẽ được gán nhãn cụm mới và tất cả các hàng xóm của nó cũng sẽ được cấp cùng một nhãn. Hàm phù hợp sẽ nhập một vòng lặp while thêm tất cả các hàng xóm vào Hàng đợi để chúng có thể được gắn nhãn chính xác là một phần của cụm mới cùng với các hàng xóm của hàng xóm mới được tìm thấy

Quá trình này sẽ tiếp tục cho đến khi thuật toán đã kiểm tra tất cả các điểm

def predict():

Khi đưa ra dự đoán, thuật toán sẽ xác định xem điểm đầu vào mới có hàng xóm nào hay không bằng cách sử dụng rangeQuery. Nếu đúng như vậy, thì điểm mới sẽ được dự đoán có cùng nhãn với các điểm lân cận của nó

Đây là những gì lớp học đã hoàn thành của chúng tôi trông như thế nào

Làm thế nào để nó so sánh với phiên bản Scikit-Learn?

Như mong đợi, quá trình triển khai của chúng tôi từ đầu có kết quả giống như phiên bản Scikit-Learn. Phiên bản DBSCAN của chúng tôi mất nhiều thời gian hơn và tôi vẫn sẽ sử dụng phiên bản Scikit-Learns, nhưng hy vọng việc triển khai thuật toán từ đầu đã giúp bạn hiểu rõ hơn về cách tìm thấy các hình dạng cụm tùy ý bằng cách sử dụng DBSCAN