密度聚类算法python实现
时间: 2023-10-08 09:14:53 浏览: 46
密度聚类(Density-Based Clustering)是一种基于密度的聚类算法,它可以发现任意形状的聚类。它的基本思想是,如果一个点的密度大于某个阈值,那么它就是一个核心点(Core Point),并且与其距离在一定范围内的点都属于同一簇;如果一个点的密度小于某个阈值,但是与某个核心点距离在一定范围内,那么它就是一个边界点(Border Point),并且属于与该核心点相同的簇;如果一个点的密度小于某个阈值,并且与任何核心点距离都大于该阈值,那么它就是一个噪音点(Noise Point)。
以下是一种基于Python的密度聚类算法实现:
```python
import numpy as np
class DBSCAN:
def __init__(self, eps=0.5, min_samples=5):
self.eps = eps
self.min_samples = min_samples
def fit(self, X):
n = X.shape[0]
labels = np.zeros(n)
cluster = 0
for i in range(n):
if labels[i] != 0:
continue
neighbors = self.region_query(X, i)
if len(neighbors) < self.min_samples:
labels[i] = -1
continue
cluster += 1
labels[i] = cluster
self.expand_cluster(X, labels, i, neighbors, cluster)
return labels
def expand_cluster(self, X, labels, i, neighbors, cluster):
for j in neighbors:
if labels[j] == -1:
labels[j] = cluster
elif labels[j] == 0:
labels[j] = cluster
j_neighbors = self.region_query(X, j)
if len(j_neighbors) >= self.min_samples:
neighbors = np.concatenate((neighbors, j_neighbors))
return
def region_query(self, X, i):
return np.where(np.linalg.norm(X - X[i], axis=1) < self.eps)[0]
```
其中,eps和min_samples分别代表密度半径和最小样本数。fit方法接受一个n * d的矩阵X作为输入,返回一个长度为n的一维数组,代表每个样本所属的簇,-1代表噪音点。
该算法的时间复杂度为O(n^2),但是可以通过一些优化来降低复杂度。