Поиск по сетке над кубом/сферой в R^n

Я пытаюсь реализовать поиск по сетке (на Python, если это имеет значение) по сфере в R^n , где n неизвестно.

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

Я также готов рассмотреть поиск куба, повторяя ТОЛЬКО грани куба. (А именно, повторение L_inf сферы)

Если бы я знал, что n=2, я бы сделал следующее:

import numpy as np

def enumerate_2d_sphere(R,theta,center=(0,0)):
    for n in xrange(int(2*np.pi / theta)+1):
        degree = n*theta
        point =(center[0]+R*np.cos(degree),center[1]+R*np.sin(degree))
        yield point

for p in enumerate_2d_sphere(1,0.1):
    print p

Поскольку n может быть сколь угодно большим, я ищу способ эффективно перебирать сферу\куб.

Любые идеи?

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

В итоге я использовал модифицированную версию того, что предложил Струбли:

import itertools
import numpy as np
import matplotlib.pyplot as plt

def f(d, center, scale=1):
    dim = len(center)
    print d/-2.0
    diff = scale * np.array([d/-2.0 for _ in xrange(dim)])
    bias = diff + center
    for i in range(dim):
        l = ([ xrange(1,d) for _ in xrange(i)] +
             [[0,d]] +
             [ xrange(d+1) for _ in xrange(dim-i-1)]
            )
        for r in itertools.product(*l):
            yield scale*np.array(r)+bias
#example for R^2:
center = (1,1.5)
data = np.array([x for x in f(20,center,scale = 0.1)])


plt.scatter(data[:,0], data[:,1],color='r',s=100,alpha=0.5)
plt.scatter(center[0], center[1],color='b',s=300,alpha=0.5)
plt.show()

Выходная цифра:

введите здесь описание изображения

Еще один вариант — генерировать равномерно распределенные выборки на сфере. Обратите внимание, что количество выборок определяет «плотность» (или ожидаемую плотность) точек:

import numpy as np
def generate_random_points(R,center,quantity=1000):
    """
    :param R: float
    :param center: np.array
    :param quantity: int
    """
    dim = len(center)
    for n in xrange(quantity):
        s = np.random.normal(0, 1,dim)
        r = np.sqrt(np.dot(s,s))
        s = (R/r) * s
        yield s+center

Наихудшим методом (с точки зрения простоты и эффективности) было бы создание точек на сфере с помощью перечисление n-1 углов. Недостаток эффективности вытекает из необходимости часто рассчитывать произведения sin и cos (хотя и это можно взломать)


python hyperparameters grid-search
person omerbp    schedule 28.02.2016    source источник
comment
Можете ли вы объяснить немного больше, что вы хотите? Например, предположим, что R=10, n=2, c=(0, 0), theta=1. Что значит представить все точки этого диска как функцию R, c и тета?   -  person Paul Hankin    schedule 28.02.2016

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете использовать сферические координаты в n измерениях (см., например, wikipedia), или вы можете использовать евклидовы координаты, просто задав последней координате значение, необходимое для получения правильного радиуса (плюс или минус). Оба они являются прекрасными параметризациями и дадут вам все точки на сфере с правильным количеством параметров для повторения.

Но они не ведут естественным образом к элементу постоянной площади (объема) — в чем легко убедиться, просто подумав о 3-сфере. У этой проблемы нет простого решения.

Я думаю, что возможным подходом было бы использование параметризации n-1-мерной сетки, но разделение n-го компонента на переменное количество значений в зависимости от объема.

С гранями n-куба проще: достаточно сгенерировать n пар граней, где n-я координата минимальна или максимальна. Так, например, рассматривая n-куб размера 1, начиная с начала координат:

Установите первую координату на ноль и пронумеруйте сетку по оставшейся части. Затем установите его на один и сделайте это снова. Затем повторите для второй координаты. И так далее.

Вот простой способ сделать это с помощью itertools.product. Я масштабировал поле в целочисленные координаты для простоты и эффективности: вам нужно изменить масштаб и переместить центр. Таким образом, n — это количество измерений, а d — количество подразделений по каждой оси.

import itertools

def f(n,d):

    for i in range(n):
        l = ([ range(1,d-1) for _ in range(i)] +
             [[0,d-1]] +
             [ range(d) for _ in range(n-i-1)]
            )
        for r in itertools.product(*l):
            yield r

print(list(f(4,3)))
person strubbly    schedule 28.02.2016
comment
Пример того, что я имел в виду под масштабированием по поверхности, а не по объему - подумайте об алгоритме, который генерирует все точки внутри шара и отбрасывает все точки, лежащие внутри шара. Ваше решение можно реализовать только с помощью рекурсии, верно? - person omerbp; 28.02.2016
comment
Ну, я думаю, что это было бы легко с рекурсией, но нет, не нужно. Например, вы можете использовать itertools.product или написать свой собственный эквивалент. - person strubbly; 28.02.2016
comment
Спасибо за ваш ответ. Я исправил часть вашего кода, так как в нем была ошибка, вы можете увидеть это в моем исходном вопросе. Спасибо! - person omerbp; 28.02.2016
comment
Ааа, хорошо подмечено - классика с одной ошибкой! Я также исправил это в своем ответе. - person strubbly; 29.02.2016

arrow_upward
0
arrow_downward

Я не думаю, что функция поиска сетки sklearn имеет эту опцию, но реализовать ее вручную не должно быть сложно.

  • перебирать значения n
  • для каждого n перебрать n различных угловых параметров с тета-шагом от 0 до 360
  • если вам не нужен объем сферы, также выполните итерацию по радиусу - если вам нужна только поверхность, оставьте радиус постоянным
person Ophir Yoktan    schedule 28.02.2016
comment
Размерность n неизвестна до запуска, поэтому углов может быть гораздо больше, чем два... - person omerbp; 28.02.2016
comment
Не заметил этого ... это должен быть поиск по сетке или ручной код тоже подойдет? - person Ophir Yoktan; 28.02.2016
comment
Обратите внимание, что в 3D один шаг угла изменяется от 0 до 360, а другой от 0 до 180, и я не уверен, что происходит в n измерениях... - person omerbp; 28.02.2016