BallTree

classsklearn.neighbors.BallTree

BallTree для быстрого решения обобщённых задач с N точками

Подробнее см. в Руководстве пользователя.

Параметры:

Xмассивоподобный объект формы (n_samples, n_features)

n_samples — количество точек в наборе данных, а n_features — размерность пространства параметров. Примечание: если X — массив чисел двойной точности с непрерывным расположением в памяти в порядке C, данные не будут копироваться. В противном случае будет создана внутренняя копия.

leaf_sizeположительное целое число, по умолчанию=40

Количество точек, при котором выполняется переход к полному перебору. Изменение leaf_size не влияет на результаты запроса, но может существенно повлиять на его скорость и объём памяти, необходимый для хранения построенного дерева. Объём памяти, необходимый для хранения дерева, приблизительно пропорционален n_samples / leaf_size. Для заданного leaf_size гарантируется, что листовой узел удовлетворяет leaf_size <= n_points <= 2 * leaf_size, за исключением случая, когда n_samples < leaf_size.

metricстрока или объект DistanceMetric64, по умолчанию=’minkowski’

Метрика, используемая для вычисления расстояния. По умолчанию используется “minkowski”, которая при p = 2 соответствует стандартному евклидову расстоянию. Список допустимых метрик для BallTree задаётся атрибутом valid_metrics. Дополнительные сведения о любой метрике расстояния см. в документации scipy.spatial.distance и в списке метрик в distance_metrics.

Дополнительные ключевые аргументы передаются классу метрики расстояния.

Примечание: вызываемые функции в параметре metric НЕ поддерживаются для KDTree

и Ball Tree. Накладные расходы на вызов функции приведут к очень низкой производительности.

Атрибуты:

dataпредставление памяти

Обучающие данные

valid_metrics: список строк

Список допустимых метрик расстояния.

Примеры

Запрос k ближайших соседей

>>> import numpy as np
>>> from sklearn.neighbors import BallTree
>>> rng = np.random.RandomState(0)
>>> X = rng.random_sample((10, 3))  # 10 points in 3 dimensions
>>> tree = BallTree(X, leaf_size=2)
>>> dist, ind = tree.query(X[:1], k=3)
>>> print(ind)  # indices of 3 closest neighbors
[0 3 1]
>>> print(dist)  # distances to 3 closest neighbors
[ 0.          0.19662693  0.29473397]

Сериализация и десериализация дерева с помощью pickle. Обратите внимание, что состояние дерева сохраняется при сериализации: после десериализации дерево не нужно строить заново.

>>> import numpy as np
>>> import pickle
>>> rng = np.random.RandomState(0)
>>> X = rng.random_sample((10, 3))  # 10 points in 3 dimensions
>>> tree = BallTree(X, leaf_size=2)
>>> s = pickle.dumps(tree)
>>> tree_copy = pickle.loads(s)
>>> dist, ind = tree_copy.query(X[:1], k=3)
>>> print(ind)  # indices of 3 closest neighbors
[0 3 1]
>>> print(dist)  # distances to 3 closest neighbors
[ 0.          0.19662693  0.29473397]

Запрос соседей в пределах заданного радиуса

>>> import numpy as np
>>> rng = np.random.RandomState(0)
>>> X = rng.random_sample((10, 3))  # 10 points in 3 dimensions
>>> tree = BallTree(X, leaf_size=2)
>>> print(tree.query_radius(X[:1], r=0.3, count_only=True))
3
>>> ind = tree.query_radius(X[:1], r=0.3)
>>> print(ind)  # indices of neighbors within distance 0.3
[3 0 1]

Вычисление оценки плотности с гауссовым ядром:

>>> import numpy as np
>>> rng = np.random.RandomState(42)
>>> X = rng.random_sample((100, 3))
>>> tree = BallTree(X)
>>> tree.kernel_density(X[:3], h=0.1, kernel='gaussian')
array([ 6.94114649,  7.83281226,  7.2071716 ])

Вычисление функции автокорреляции двух точек

>>> import numpy as np
>>> rng = np.random.RandomState(0)
>>> X = rng.random_sample((30, 3))
>>> r = np.linspace(0, 1, 5)
>>> tree = BallTree(X)
>>> tree.two_point_correlation(X, r)
array([ 30,  62, 278, 580, 820])

get_arrays()

Получить массивы данных и узлов.

Возвращает:

arrays: кортеж массивов

Массивы для хранения данных дерева, индексов, данных узлов и границ узлов.

get_n_calls()

Получить количество вызовов.

Возвращает:

n_calls: целое число

количество вызовов вычисления расстояния

get_tree_stats()

Получить статистику дерева.

Возвращает:

tree_stats: кортеж целых чисел

(количество отсечений, количество листьев, количество разбиений)

kernel_density(X, h, kernel='gaussian', atol=0, rtol=1E-8, breadth_first=True, return_log=False)

Вычислить оценку плотности ядра в точках X с заданным ядром, используя метрику расстояния, указанную при создании дерева.

Параметры:

Xмассивоподобный объект формы (n_samples, n_features)

Массив точек для запроса. Последняя размерность должна совпадать с размерностью обучающих данных.

hвещественное число

ширина полосы ядра

kernelстрока, по умолчанию=”gaussian”

задаёт используемое ядро. Доступны варианты: ‘gaussian’, ‘tophat’, ‘epanechnikov’, ‘exponential’, ‘linear’, ‘cosine’. По умолчанию kernel = ‘gaussian’

atolвещественное число, по умолчанию=0

Задаёт требуемую абсолютную точность результата. Если истинный результат равен K_true, то возвращаемый результат K_ret удовлетворяет условию abs(K_true - K_ret) < atol + rtol * K_ret По умолчанию равно нулю (то есть соответствует машинной точности).

rtolвещественное число, по умолчанию=1e-8

Задаёт требуемую относительную точность результата. Если истинный результат равен K_true, то возвращаемый результат K_ret удовлетворяет условию abs(K_true - K_ret) < atol + rtol * K_ret По умолчанию равно 1e-8 (то есть соответствует машинной точности).

breadth_firstлогическое значение, по умолчанию=False

Если True, используется поиск в ширину. Если False (значение по умолчанию), используется поиск в глубину. Поиск в ширину обычно быстрее для компактных ядер и/или при высокой точности.

return_logлогическое значение, по умолчанию=False

Возвращать логарифм результата. Для узких ядер это может быть точнее, чем возвращать сам результат.

Возвращает:

densityndarray формы X.shape[:-1]

Массив значений плотности (или логарифма плотности)

query(X, k=1, return_distance=True, dualtree=False, breadth_first=False)

Выполнить запрос к дереву для поиска k ближайших соседей

Параметры:

Xмассивоподобный объект формы (n_samples, n_features)

Массив точек для запроса

kцелое число, по умолчанию=1

Количество ближайших соседей для возврата

return_distanceлогическое значение, по умолчанию=True

если True, возвращается кортеж (d, i) с расстояниями и индексами; если False, возвращается массив i

dualtreeлогическое значение, по умолчанию=False

если True, для запроса используется метод двойного дерева: для точек запроса строится дерево, а пара деревьев используется для эффективного поиска в этом пространстве. Это может повысить производительность при большом количестве точек.

breadth_firstлогическое значение, по умолчанию=False

если True, узлы запрашиваются в порядке обхода в ширину. В противном случае узлы запрашиваются в порядке обхода в глубину.

sort_resultsлогическое значение, по умолчанию=True

если True, расстояния и индексы для каждой точки сортируются перед возвратом, поэтому в первом столбце находятся ближайшие точки. В противном случае соседи возвращаются в произвольном порядке.

Возвращает:

iесли return_distance == False

(d,i)если return_distance == True

dndarray формы X.shape[:-1] + (k,), dtype=double

Каждый элемент содержит список расстояний до соседей соответствующей точки.

indarray формы X.shape[:-1] + (k,), dtype=int

Каждый элемент содержит список индексов соседей соответствующей точки.

query_radius(X, r, return_distance=False, count_only=False, sort_results=False)

Выполнить запрос к дереву для поиска соседей в пределах радиуса r

Параметры:

Xмассивоподобный объект формы (n_samples, n_features)

Массив точек для запроса

rрасстояние, в пределах которого возвращаются соседи

r может быть одним значением или массивом значений формы x.shape[:-1], если для каждой точки требуется задать свой радиус.

return_distanceлогическое значение, по умолчанию=False

если True, возвращаются расстояния до соседей каждой точки; если False, возвращаются только соседи. Обратите внимание: в отличие от метода query(), установка return_distance=True в этом случае увеличивает время вычислений. При return_distance=False нет необходимости вычислять все расстояния явно. По умолчанию результаты не сортируются: см. ключевой аргумент sort_results.

count_onlyлогическое значение, по умолчанию=False

если True, возвращается только количество точек на расстоянии не более r; если False, возвращаются индексы всех точек на расстоянии не более r. Если return_distance==True, установка count_only=True приведёт к ошибке.

sort_resultsлогическое значение, по умолчанию=False

если True, расстояния и индексы сортируются перед возвратом. Если False, результаты не сортируются. Если return_distance == False, установка sort_results = True приведёт к ошибке.

Возвращает:

countесли count_only == True

indесли count_only == False и return_distance == False

(ind, dist)если count_only == False и return_distance == True

countndarray формы X.shape[:-1], dtype=int

Каждый элемент содержит количество соседей соответствующей точки на расстоянии не более r.

indndarray формы X.shape[:-1], dtype=object

Каждый элемент — целочисленный массив numpy со списком индексов соседей соответствующей точки. Обратите внимание: в отличие от результатов запроса k ближайших соседей, возвращаемые соседи по умолчанию не сортируются по расстоянию.

distndarray формы X.shape[:-1], dtype=object

Каждый элемент — массив чисел двойной точности numpy со списком расстояний, соответствующих индексам в i.

reset_n_calls()

Сбросить количество вызовов до 0.

two_point_correlation(X, r, dualtree=False)

Вычислить функцию корреляции двух точек

Параметры:

Xмассивоподобный объект формы (n_samples, n_features)

Массив точек для запроса. Последняя размерность должна совпадать с размерностью обучающих данных.

rмассивоподобный объект

Одномерный массив расстояний

dualtreeлогическое значение, по умолчанию=False

Если True, используется алгоритм двойного дерева. В противном случае используется алгоритм с одним деревом. Алгоритмы двойного дерева могут лучше масштабироваться при больших значениях N.

Возвращает:

countsndarray

counts[i] содержит количество пар точек, расстояние между которыми меньше или равно r[i]