Предположим, у меня есть облако точек, заданное в 6-мерном пространстве, которое я могу сделать настолько плотным, насколько это необходимо. Эти точки оказываются лежащими на поверхности многогранника меньшей размерности (т. е. точечные векторы (x1, x2, ... x6) оказываются компланарными).
Я хотел бы найти вершины этого неизвестного многогранника, и моя текущая попытка использует алгоритм qhull через интерфейс scipy в Python. Вначале я получал только сообщения об ошибках, по-видимому, вызванные вводом более низкого измерения и/или множеством вырожденных точек. Я попробовал пару методов грубой силы для устранения вырожденных точек, но не очень успешно, и поэтому, в конце концов, я предполагаю, что все эти точки должны лежать на выпуклой оболочке.
Этот вопрос был очень полезно, так как предполагает уменьшение размерности с помощью анализа основных компонентов. Если я проецирую точки на 4D-гиперплоскость, алгоритм qhull работает без ошибок (для любого более высокого измерения он не работает).
from scipy.spatial import ConvexHull
from sklearn.decomposition import PCA
model = PCA(n_components=4).fit(initial_points)
proj_points = model.transform(initial_points)
hull = ConvexHull(proj_points, qhull_options = "Qx")
В ответе на вопрос выше упоминается, что симплексы необходимо преобразовать обратно после вычисления выпуклой оболочки проецируемых точек. Но вывод qhull состоит только из индексов, и почему они не совпадают с индексами начальных точек?
Теперь моя проблема в том, что я не знаю, какую точность использовать для получения правильных вершин. Независимо от того, насколько плотным я создаю облако точек, полученные вершины различаются с разной точностью. Например, для начальных точек в массиве (10000, 6) я получаю (где E0,03 — максимум, для которого это работает):
hull1 = ConvexHull(proj_points, qhull_options = "Qx, E0.03")
print len(hull1.vertices)
print hull1.vertices
5
[ 437 2116 3978 7519 9381]
И начертить его в какой-нибудь (не очень информативной) проекции осей 0,1,2 (где синие точки представляют выборку начального облака точек):
Но для большей точности (конечно) я получаю другой набор:
hull2 = ConvexHull(proj_points, qhull_options = "Qx, E0.003")
print len(hull2.vertices)
print hull2.vertices
29
[ 74 75 436 437 756 1117 2116 2366 2618 2937 3297 3615 3616 3978 3979
4340 4561 4657 4659 4924 5338 5797 6336 7519 7882 8200 9381 9427 9470]
Та же проекция (только немного другой ракурс):
Я подозреваю, что на первом изображении недостаточно вершин, а на втором изображении, возможно, слишком много. Хотя, конечно, я не могу извлечь из этих графиков точную информацию. Но есть ли хороший способ узнать, какую точность использовать? Или, может быть, совершенно другой подход к этой проблеме (я уже попробовал несколько)?