Почему DBSCAN.fit () быстрее с большим количеством функций? - PullRequest
Новая
       74

Почему DBSCAN.fit () быстрее с большим количеством функций?

3 голосов
/ 18 февраля 2020

Я играю с DBSCAN . Мне интересно, почему время выполнения уменьшается с увеличением количества функций (см. График ниже). Я ожидаю, что время выполнения увеличится с увеличением числа функций ... 

import timeit
import functools
import numpy as np
import matplotlib.pyplot as plt
from sklearn.metrics.pairwise import euclidean_distances
from sklearn.cluster import DBSCAN

features = [2, 4, 8, 10]
training_examples = [100, 500, 1000,2000]
n_iterations = 10

x = np.asarray(training_examples)

for num_features in features:

    average_execution_time = []

    for num_training_examples in training_examples:
        # generate matrix of random training examples
        X = np.random.rand(num_training_examples, num_features)

        # generate a symmetric distance matrix
        D = euclidean_distances(X, X)

        # DBSCAN parameters
        eps = 0.5
        kmedian_thresh = 0.005
        min_samples = 5

        db = DBSCAN(eps=eps,
                    min_samples=min_samples,
                    metric='precomputed')

        # Call timeit
        t = timeit.Timer(functools.partial(db.fit, D))

        average_execution_time.append(t.timeit(n_iterations) / n_iterations)

    y = np.asarray(average_execution_time)

    plt.plot(x, y, label='{} features'.format(num_features))

plt.xlabel('No. of Training Examples')
plt.ylabel('DBSCAN.fit() time to Cluster')
plt.title('DBSCAN.fit() avg time to Cluster')
plt.legend()
plt.grid()
plt.show()

enter image description here

1 Ответ

1 голос
/ 02 марта 2020

Алгоритм DBSCAN в основном требует 2 параметра: 

eps: specifies how close points should be to each other to be considered a part of a cluster. It means that if the distance between two points is lower or equal to this value (eps), these points are considered neighbors.

minPoints: the minimum number of points to form a dense region. For example, if we set the minPoints parameter as 5, then we need at least 5 points to form a dense region.

Я думаю, что ваш вопрос связан с обоими типами параметров.

eps: если выбранное значение eps слишком мало, Большая часть данных не будет кластеризована. Это будет считаться выбросами, потому что не удовлетворяет количеству точек для создания плотной области. С другой стороны, если выбранное значение слишком велико, кластеры будут объединяться, и большинство объектов будут находиться в одном кластере. EPS следует выбирать на основе расстояния набора данных (мы можем использовать график k-расстояния, чтобы найти его), но в целом небольшие значения eps предпочтительны. Как правило, больше = быстрее.

minPoints: Как правило, минимальные minPoints могут быть получены из числа измерений (D) в наборе данных, например minPoints ≥ D + 1. Большие значения обычно лучше для наборов данных с шумом и будет формировать более значимые кластеры. Минимальное значение для minPoints должно быть 3, но чем больше набор данных, тем больше значение minPoints, которое следует выбрать. В основном, больше = быстрее.

...