DBSCAN phân cụm Python

DBSCAN là một thuật toán phân cụm rất nổi tiếng bởi vì, không giống như các thuật toán phân cụm khác như Kmeans, nó có thể phân cụm chính xác các hình dạng dữ liệu phức tạp. Vì vậy, trong bài đăng này, bạn sẽ học cách sử dụng thuật toán DBSCAN trong Python. Cụ thể hơn trong bài chúng ta sẽ thấy

1. Thuật toán DBSCAN là gì và nó hoạt động như thế nào
2. Cách sử dụng thuật toán DBSCAN trong Python bằng Sklearn để tìm hiểu cách nó được triển khai trong đời thực
3. Tìm hiểu cách chọn đúng siêu tham số mô hình
4. Tìm hiểu cách lập trình thuật toán DBSCAN từ đầu bằng Python

Âm thanh thú vị?

Cách thức hoạt động của thuật toán DBSCAN

Giới thiệu về mật độ

Chính cái tên DBSCAN cho chúng ta biết thuật toán hoạt động như thế nào. DBSCAN xuất phát từ các từ Cụm ứng dụng không gian dựa trên mật độ, nghĩa là, nó là một thuật toán phân cụm dựa trên mật độ

Theo nghĩa này, mật độ đề cập đến số lượng quan sát mà chúng ta có trong cùng một khu vực. Để cung cấp cho bạn một ý tưởng, trong hình ảnh sau đây, tôi bao gồm hai vùng, một vùng có mật độ điểm và vùng khác không có điểm

Tuy nhiên, nếu bạn dừng lại để suy nghĩ về nó, khái niệm về mật độ có một chút chủ quan. Bởi vì, cần bao nhiêu điểm để coi một khu vực là “đậm đặc”?

Chính xác là cả số điểm để coi một khu vực là dày đặc, cũng như khoảng cách mà các điểm này được tìm thấy là hai siêu tham số của mô hình

Hiểu được điều này, hãy xem thuật toán DBSCAN hoạt động như thế nào

DBSCAN hoạt động như thế nào

Hoạt động của thuật toán DBSCAN dựa trên việc phân loại các quan sát thành ba loại

• điểm cốt lõi. là những điểm tuân thủ các điều kiện mật độ mà chúng tôi đã đặt
• điểm có thể đạt được. là những điểm thậm chí không đáp ứng các điều kiện về mật độ, nhưng gần với các điểm cốt lõi khác
• Tiếng ồn. là những điểm không thỏa mãn điều kiện về mật độ và hơn nữa trong bán kính của chúng không có điểm nào khác

Vì vậy, DBSCAN dựa trên những điều sau đây

1. Tính ma trận khoảng cách giữa các điểm khác nhau. Khoảng cách Euclide thường được sử dụng, mặc dù những khoảng cách khác có thể được sử dụng
2. Có tính đến các tham số của mô hình, nó phân loại từng điểm giữa điểm lõi, điểm biên và nhiễu. Theo nghĩa này, các điểm cốt lõi khác nhau có thể xuất hiện do có thể có một số vùng mật độ. Mỗi điểm cốt lõi đó sẽ thuộc về một cụm
3. Chỉ định các lõi có thể truy cập của từng cụm cho cụm

Trong hình ảnh sau đây, bạn có thể thấy dễ dàng hơn cách thức hoạt động của thuật toán

Ưu điểm và nhược điểm của DBSCAN

Như bạn có thể thấy, hoạt động của thuật toán DBSCAN khá đơn giản. Mặc dù vậy, nó là một thuật toán rất tốt vì nó có những ưu điểm sau

1. Nó có thể phát hiện các hình dạng hình học phức tạp mà các mô hình phân cụm khác không thể phát hiện được
2. Nó không bị ảnh hưởng bởi các ngoại lệ >, vì nó có thể quản lý chúng một cách chính xác
3. Bạn không phải chủ quan xác định số lượng cụm mà số lượng cụm sẽ được tạo tự động, tùy thuộc vào các tham số chúng tôi đã chọn
4. Thuật toán và các tham số của nó rất dễ hiểu, điều này sẽ giúp người dùng dễ dàng chọn các tham số tối ưu một cách trực quan hơn và do đó, thuật toán được áp dụng chính xác

Tuy nhiên, nó cũng có một số nhược điểm như

1. Nó không mang tính quyết định, vì các điểm có thể truy cập có thể đạt được bởi các cụm khác nhau và do đó, trong các lần thực thi khác nhau, chúng có thể được gán cho các cụm khác nhau
2. Trong trường hợp có nhiều vùng khác nhau và mỗi vùng có mật độ khác nhau, việc lựa chọn tham số DBSCAN có thể phức tạp

Bây giờ bạn đã biết DBSCAN là gì, cũng như những ưu điểm và nhược điểm của nó, hãy xem cách chúng ta có thể sử dụng nó với thư viện Sklearn

Nếu bạn muốn tìm hiểu sâu về cách thức hoạt động của thư viện Sklearn, tôi khuyên bạn nên đăng bài này

Cách sử dụng DBSCAN trong Python với Sklearn

Chức năng chính

Thuật toán DBSCAN có thể được tìm thấy trong mô-đun Sklearn

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Giống như các mô hình cụm còn lại của Sklearn, việc sử dụng nó bao gồm hai bước. đầu tiên,

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

from sklearn.cluster import DBSCAN

clusters = DBSCAN(eps = 3, min_samples = 5).fit_predict(data)

So Sánh Kmeans vs. DBSCAN

Vì vậy, tôi sẽ tạo một số dữ liệu thử nghiệm để xem DBSCAN hoạt động như thế nào so với một phương pháp phân cụm điển hình khác, chẳng hạn như KMeans

Để làm điều này, trước hết hãy tải các thư viện

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Khi các thư viện đã được tải, tôi sẽ tạo hàm make_circle, hàm này cho phép tôi tạo các điểm trên một đường tròn bán kính r. Ngoài ra, những điểm này không hoàn hảo mà có một số nhiễu nên chúng không phải là những đường hoàn hảo

# Genero los datos
def make_circle(r, n, noise = 30, seed = 1234):
  np.random.seed(seed)
  return [(math.cos(2*math.pi/n*x)*r+np.random.normal(-noise,noise), math.sin(2*math.pi/n*x)*r+np.random.normal(-noise,noise)) for x in range(1,n+1)]

small_circle = make_circle(100, 300, 10)
medium_circle = make_circle(300, 700, 20)
big_circle = make_circle(500, 1000, 30)

noise = [(np.random.randint(-600,600),np.random.randint(-600,600)) for i in range(300)]

Chúng tôi trực quan hóa các điểm để xem dữ liệu chúng tôi đã tạo ra như thế nào

Như bạn có thể thấy, đó là về việc phân cụm dữ liệu theo các dạng phức tạp, ngoài ra, có các ngoại lệ. Vì vậy, hãy xem loại thuật toán phân cụm như KMeans sẽ trả về

data_norm = normalize(data)

preds = KMeans(n_clusters = 3, random_state =123).fit_predict(data_norm)

cols = { 
  0: 'r',
  1: 'g',
  2: 'b'
}

data['kmeans_pred'] = [cols.get(pred) for pred in preds]
data.plot.scatter('x', 'y', c='kmeans_pred')

Như chúng ta có thể thấy, Kmeans đã thực hiện phân cụm rất tệ, vì

1. Nó chưa quản lý để phân cụm theo các hình dạng phức tạp của mô hình
2. Nó đã không tính đến việc có những ngoại lệ, bao gồm chúng trong các cụm khác nhau

Tóm lại, như bạn thấy, thuật toán kmeans không phải là mô hình tốt cho những trường hợp này. Bây giờ hãy xem mô hình DBSCAN hoạt động như thế nào

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Như chúng ta có thể thấy, thuật toán DBSCAN đã có thể phân cụm dữ liệu đầy đủ, vì

1. Bạn đã tính đến các hình dạng phức tạp của dữ liệu
2. Bạn chưa xem xét tiếng ồn trong bất kỳ cụm nào

Tuy nhiên, có một vấn đề mấu chốt ở đây, đó là trong trường hợp này tôi đã chuyển một số tham số cho mô hình, nhưng tôi chưa giải thích cách tôi chọn chúng. Hãy xem cách thực hiện

Cách chọn tham số trong DBSCAN

Để chọn tham số epsilon, tức là khoảng cách tối đa mà tại đó một quan sát khác phải được xem xét để đáp ứng tiêu chí “gần”, chúng ta phải biết các biến cách nhau gần hay xa

Thông thường sẽ có một vài biến sẽ ở rất gần nhau, và khi khoảng cách tăng lên thì số lượng biến gần nhau sẽ tăng lên. Biểu đồ đó là biểu đồ sẽ giúp chúng tôi chọn giá trị tối ưu của epsilon

Để có được biểu đồ khoảng cách, chúng tôi sẽ sử dụng mô hình Hàng xóm gần nhất của Sklearn, vì chức năng này trả về thông tin về khoảng cách đến hàng xóm gần nhất của chúng tôi

Quan trọng. nếu khi tạo DBSCAN, chúng ta xác định một hàm khoảng cách khác với khoảng cách Euclide, thì chính hàm này là những gì chúng ta sẽ phải sử dụng trong bước này để có được kết quả nhất quán

Vì vậy, hãy xem cách sử dụng kNN để tìm giá trị tối ưu của epsilon

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Với điều này, bạn biết cách tìm giá trị tối ưu của epsilon. Thật không may, không có cách nào dễ dàng để tìm ra giá trị tối ưu cho số lượng quan sát phải ở gần đó để được coi là điểm cốt lõi, vì nó sẽ phụ thuộc vào mật độ của dữ liệu

Cuối cùng, hãy xem mô hình này hoạt động chính xác như thế nào. Để làm điều này, hãy lập trình thuật toán DBSCAN từ đầu bằng Python. Chúng ta hãy đi đến đó

Cách lập trình DBSCAN từ đầu bằng Python

0. Cách tiếp cận lý thuyết

Với những gì chúng ta đã thấy cho đến nay, việc lập trình DBSCAN từ đầu bằng Python tương đối dễ dàng, vì chúng ta chỉ cần

1. Lập trình chức năng khoảng cách. Để tăng tốc độ thực hiện, chúng tôi sẽ tạo một ma trận khoảng cách
2. Định nghĩa hàm tìm hàng xóm gần nhất. Hàm này phải tính đến tham số epsilon, nghĩa là bán kính được coi là hàng xóm
3. Xác định hàm mở rộng, để nếu một giá trị được gán cho một cụm, nó sẽ kiểm tra xem các hàng xóm của nó có thuộc cụm đó hay không
4. Tạo một vòng lặp để lặp lại và đảm bảo rằng tất cả các quan sát được đánh giá

Vì vậy, khi đã thấy cách tiếp cận lý thuyết, chúng tôi đang lập trình thuật toán theo từng phần

1. Tạo ma trận khoảng cách

Chúng ta phải tạo một ma trận khoảng cách dễ thực hiện và cũng cho phép chúng ta sử dụng các loại khoảng cách khác nhau

Nếu bạn muốn tìm hiểu thêm về các phép đo khoảng cách hoặc hiểu cách hoạt động của các phép đo khoảng cách này, tôi khuyên bạn nên đọc bài đăng này

Để làm điều này, chúng tôi sẽ sử dụng mô-đun

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Mặt khác, điều quan trọng cần lưu ý là các loại khoảng cách khác nhau yêu cầu dữ liệu phải được chuẩn hóa (tìm hiểu thêm về nó tại đây). Vì vậy, tôi đã tạo một chức năng để người dùng quyết định xem anh ta có muốn chuẩn hóa dữ liệu hay không

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Hoàn hảo, chúng ta đã có một hàm cho phép chúng ta tìm ma trận khoảng cách. Bây giờ chúng ta chuyển sang điểm tiếp theo. cách tìm hàng xóm gần nhất

2. Cách tìm hàng xóm gần nhất

Bây giờ chúng ta có ma trận khoảng cách và tham số epsilon, đối với một quan sát i, những người hàng xóm gần nhất sẽ là những người có khoảng cách đến quan sát i bằng hoặc nhỏ hơn epsilon

Vì chúng ta đang làm việc với mảng Numpy, nên chúng ta có thể tạo một hàm nhận vectơ khoảng cách từ điểm đó đến các điểm còn lại và sử dụng hàm

# Genero los datos
def make_circle(r, n, noise = 30, seed = 1234):
  np.random.seed(seed)
  return [(math.cos(2*math.pi/n*x)*r+np.random.normal(-noise,noise), math.sin(2*math.pi/n*x)*r+np.random.normal(-noise,noise)) for x in range(1,n+1)]

small_circle = make_circle(100, 300, 10)
medium_circle = make_circle(300, 700, 20)
big_circle = make_circle(500, 1000, 30)

noise = [(np.random.randint(-600,600),np.random.randint(-600,600)) for i in range(300)]

Theo nghĩa này, một điều quan trọng cần lưu ý là ma trận khoảng cách bao gồm khoảng cách của một điểm với chính nó, luôn luôn bằng 0. Do đó, chúng ta sẽ phải tính đến điều này sau, khi chúng ta kiểm tra xem một quan sát có đáp ứng điều kiện có nhiều hơn x hàng xóm hay không

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Bây giờ chúng ta đã có cách tìm hàng xóm gần nhất, hãy chuyển sang phần khó nhất có lẽ là lập trình thuật toán DBSCAN. Hãy xem cách tạo chức năng mở rộng

3. Cách tạo hàm mở rộng

Hàm mở rộng dựa trên ý tưởng rằng, nếu một quan sát thuộc về một cụm, thì các quan sát duy nhất có thể thuộc về cùng một cụm là những quan sát gần với quan sát này. Đổi lại, nếu những người hàng xóm của quan sát đầu tiên thuộc về cụm, thì những người hàng xóm của những người hàng xóm cũng có thể thuộc về cụm

Như bạn có thể thấy, đây là một hàm đệ quy vì, với một số hàng xóm, tôi kiểm tra xem từng hàng xóm, tôi kiểm tra xem nó có được gán cho một cụm không. Nếu chưa thì kiểm tra xem láng giềng đó có đủ điều kiện để được gán vào cụm không

Ghi chú. Điều quan trọng là phải kiểm tra xem hàng xóm chưa được gán cho một cụm. Nếu không, chúng ta sẽ bước vào một vòng lặp vô hạn

Nếu nó thỏa mãn họ, đối với mỗi người hàng xóm, tôi sẽ áp dụng chính xác cùng một quy trình (nghĩa là cùng một chức năng)

Vì vậy, tôi đưa phần này vào lớp

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Một khi điều này được thực hiện, chúng tôi chuyển sang điểm cuối cùng. phân tích từng quan sát

4. Đánh giá tất cả các quan sát

Đánh giá tất cả các quan sát là đơn giản. bạn chỉ cần tạo một vòng lặp lặp lại cho mỗi quan sát và nếu quan sát chưa được chỉ định, hãy phân tích các lân cận và nếu các điều kiện được đáp ứng, hãy tiến hành mở rộng

Theo nghĩa này, cần phải kiểm tra xem mỗi quan sát chưa được dán nhãn chưa bởi vì có thể trường hợp quan sát đó đã được phân loại thành một cụm trong một “phần mở rộng” của cụm của một quan sát trước đó

Cuối cùng, khi chúng tôi đã duyệt qua tất cả các quan sát, chúng tôi trả về vectơ nhãn phân loại từng quan sát

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Bây giờ chúng ta đã lập trình chức năng DBSCAN từ đầu, hãy xem nó hoạt động như thế nào. Để làm điều này, chúng tôi sẽ kiểm tra chức năng với chính xác dữ liệu mà chúng tôi đã xác minh trước đó

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.preprocessing import normalize
from sklearn.cluster import KMeans, DBSCAN
import seaborn as sns
import matplotlib.pyplot as plt
from scipy.spatial import distance
from sklearn.neighbors import NearestNeighbors

Như chúng ta có thể thấy, thuật toán DBSCAN của chúng ta đã hoạt động chính xác và hơn nữa, thời gian thực hiện của nó rất thấp (1 giây). Nếu bạn đã theo dõi phần xây dựng đến đây, bạn sẽ thấy thuật toán DBSCAN dễ hiểu, sử dụng và thậm chí lập trình từ đầu trong Python dễ dàng như thế nào

DBSCAN bằng Python. phần kết luận

Tôi hy vọng bài đăng này đã giúp bạn tìm hiểu thêm về DBSCAN như một phương pháp phân cụm dữ liệu

Ngoài ra, nếu bạn muốn tìm hiểu về các loại phương pháp phân cụm khác, tôi khuyên bạn nên đọc bài đăng này, nơi tôi nói về Kmeans và cách lập trình nó từ đầu

Cuối cùng, nếu có một phương pháp phân cụm cụ thể mà bạn muốn tìm hiểu, vui lòng liên hệ với tôi và nếu tôi biết về nó, tôi sẽ viết một bài về nó

Tôi hy vọng rằng bài viết hữu ích cho bạn và bạn thích nó. Nếu vậy, tôi khuyến khích bạn đăng ký để cập nhật những bài viết mà tôi tải lên blog. Hẹn gặp lại bạn trong lần tiếp theo

Làm cách nào để phân cụm bằng DBSCAN trong Python?

DBSCAN hay K cái nào tốt hơn

Giải thích phân cụm DBSCAN bằng ví dụ là gì?

Hdbscan có tốt hơn DBSCAN không?