Интерпретация DBSCAN
Полное написание DBSCAN:
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.
Этот алгоритм представляет собой алгоритм кластеризации против шума, основанный на кластеризации плотности.
Алгоритм разбит на два шага
Первый большой шаг:
Найдите основные точки для формирования временных кластеров
Соответствующий исходный код
neighbors_model = NearestNeighbors(
radius=self.eps,
algorithm=self.algorithm,
leaf_size=self.leaf_size,
metric=self.metric,
metric_params=self.metric_params,
p=self.p,
n_jobs=self.n_jobs,
)
neighbors_model.fit(X)
# This has worst case O(n^2) memory complexity
neighborhoods = neighbors_model.radius_neighbors(X, return_distance=False)
интерпретировать
Сканировать все точки выборки, если количество точек в пределах радиуса eps определенной точки выборки >= min_samples, она будет включена в список основных точек, а точки, плотность которых достигнута напрямую, образуют соответствующий временный кластер.
Второй важный шаг: Объедините временные кластеры, чтобы получить кластеры
core_samples = np.asarray(n_neighbors >= self.min_samples, dtype=np.uint8)
dbscan_inner(core_samples, neighborhoods, labels)
Среди них dbscan_inner находится в _dbscan_inner.pyx (файл .pyx аналогичен файлу исходного кода .c на языке C, а исходный код модуля Cython в файле .pyx скомпилирован в файл .c для выполнения расчета ускорение) Вычисление функции dbscan_inner является ядром алгоритма DBSCAN. С помощью [стека] поиск в глубину начинается с i, что очень похоже на классический алгоритм расчета связности компоненты, разница в том, что неосновные точки помечаются как часть кластера, но не расширяют своих соседей.
while True:
if labels[i] == -1:
labels[i] = label_num
if is_core[i]:
neighb = neighborhoods[i]
for i in range(neighb.shape[0]):
v = neighb[i]
if labels[v] == -1:
push(stack, v)
if stack.size() == 0:
break
i = stack.back()
stack.pop_back()
Вопросы, о которых следует знать:
- the parameter min_samples primarily controls how tolerant the algorithm is towards noise.the parameter eps is crucial to choose appropriately for the data set and distance function and usually cannot be left at the default value.
Радиус окрестности eps и минимальное количество точек min_samples. Эти два параметра алгоритма управляют эффектом кластеризации и не могут использовать значения по умолчанию.
2.the clusters to which non-core samples are assigned can differ depending on the data order. This would happen when a non-core sample has a distance lower than eps to two core samples in different clusters.
Это еще одна проблема, которую часто упускают из виду. Когда данные предоставляются в другом порядке, результаты кластеризации могут быть разными! См.:GitHub.com/Irving C/ Ни…Проблема граничной точки: (тяжелее, чем Kmeans) Расстояние между точкой выборки и двумя основными объектами меньше, чем eps, но основные объекты не являются непосредственно плотными и не принадлежат к одному и тому же кластеру. Как мы должны это определить? Во-первых, категория кластеризации пометит этот образец как свою категорию
3. Другое metric, metric_params=None, algorithm="auto", leaf_size=30, p=2, несколько параметров определяют метод расчета расстояния между точками выборки, по умолчанию используется расчет евклидова расстояния полного обхода. Параметр sample_weight соответствует каждому весу каждой sample, значение по умолчанию равно 1, чем больше значение, тем больше она может способствовать тому, чтобы стать основной точкой выборки, в противном случае она может препятствовать тому, чтобы стать основной точкой выборки n_jobs Следует ли распараллеливать вычисления.