KDTree

classsklearn.neighbors.KDTree

KDTree для быстрых обобщённых задач N-точек

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

Параметры:

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

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

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. Список допустимых метрик для KDTree представлен атрибутом valid_metrics. См. документацию scipy.spatial.distance и метрики, указанные в distance_metrics для получения дополнительной информации о любой метрике расстояния.

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

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

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

Атрибуты:

dataвид памяти

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

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

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

Примеры

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

>>> import numpy as np
>>> from sklearn.neighbors import KDTree
>>> rng = np.random.RandomState(0)
>>> X = rng.random_sample((10, 3))  # 10 points in 3 dimensions
>>> tree = KDTree(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]

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

>>> import numpy as np
>>> import pickle
>>> rng = np.random.RandomState(0)
>>> X = rng.random_sample((10, 3))  # 10 points in 3 dimensions
>>> tree = KDTree(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 = KDTree(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 = KDTree(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 = KDTree(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

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

Возвращает:

densityмассив формы 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

dмассив формы X.shape[:-1] + (k,), тип=double

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

iмассив формы X.shape[:-1] + (k,), тип=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_distancebool, по умолчанию=False

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

count_onlybool, по умолчанию=False

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

sort_resultsbool, по умолчанию=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

countмассив ndarray формы X.shape[:-1], тип данных=int

Каждая запись содержит количество соседей в пределах расстояния r от соответствующей точки.

indмассив ndarray формы X.shape[:-1], тип данных=object

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

distмассив ndarray формы X.shape[:-1], тип данных=object

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

reset_n_calls()

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

two_point_correlation(X, r, dualtree=False)

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

Параметры:

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

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

rмассив-подобный

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

dualtreebool, по умолчанию=False

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

Возвращаемое значение:

countsмассив ndarray

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