A Диаграмма Вороного (график разложения Вороного) - это один из способов визуального представления матрицы расстояний (DM).
Их также просто создавать и создавать с помощью R - вы можете сделать оба в одной строке кода R.
Если вы не знакомы с этим аспектом вычислительной геометрии, отношения между ними (VD & DM) просты, хотя краткое резюме может быть полезным.
Матрицы расстояний - то есть двумерная матрица, показывающая расстояние между точкой и любой другой точкой, является промежуточным выходным сигналом при вычислении kNN (т. Е. K-ближайший сосед, алгоритм машинного обучения, который прогнозирует значение заданных данных точка, основанная на средневзвешенном значении ближайших соседей «k», по расстоянию, где «k» - некоторое целое число, обычно от 3 до 5.)
kNN концептуально очень прост - каждая точка данных в вашем тренировочном наборе, по сути, является «позицией» в некотором n-мерном пространстве, поэтому следующим шагом является вычисление расстояния между каждой точкой и каждой другой точкой с использованием некоторого расстояния метрика (например, евклидова, манхэттенская и т. д.). Хотя этап обучения, т. Е. Построение матрицы расстояний, является простым, его использование для прогнозирования значения новых точек данных практически обременено поиском данных - нахождение ближайших 3 или 4 точек из нескольких тысяч или нескольких миллионов разбросаны в n-мерном пространстве.
Для решения этой проблемы обычно используются две структуры данных: kd-деревья и разложения Ворони (т. Е. «Тесселяция Дирихле»).
Разложение Вороного (VD) однозначно определяется матрицей расстояний - то есть, есть карта 1: 1; действительно, это визуальное представление матрицы расстояний, хотя, опять же, это не является их целью - их основная цель - эффективное хранение данных, используемых для прогнозирования на основе kNN.
Кроме того, будет ли хорошей идеей представлять матрицу расстояний таким образом, вероятно, больше всего зависит от вашей аудитории. Для большинства связь между VD и предшествующей матрицей расстояний не будет интуитивной. Но это не делает его неверным - если кто-то без какой-либо подготовки по статистике хотел знать, имеют ли две группы населения одинаковое распределение вероятностей, и вы показали им график Q-Q, они, вероятно, подумали бы, что вы не ответили на их вопрос. Поэтому для тех, кто знает, на что они смотрят, VD - это компактное, полное и точное представление DM.
Так, как вы делаете один?
Декомпозиция Вороного строится путем выбора (обычно случайным образом) поднабора точек из обучающего набора (это число варьируется в зависимости от обстоятельств, но если у нас было 1 000 000 баллов, то 100 является разумным числом для этого поднабора). Эти 100 точек данных являются центрами Вороного («ВК»).
Основная идея, лежащая в основе декомпозиции Вороного, заключается в том, что вместо того, чтобы просеивать 1 000 000 точек данных, чтобы найти ближайших соседей, вам нужно только взглянуть на эти 100, а затем, как только вы найдете ближайший виртуальный канал, ваш поиск фактического ближайшие соседи ограничены только точками в этой ячейке Вороного. Затем для каждой точки данных в обучающем наборе рассчитайте VC, к которому он ближе всего. Наконец, для каждого VC и связанных с ним точек, вычислите выпуклый корпус - концептуально, только внешнюю границу, образованную назначенными точками этого VC, которые находятся дальше всего от VC. Эта выпуклая оболочка вокруг центра Вороного образует «ячейку Вороного». Полный VD является результатом применения этих трех шагов к каждому VC в вашем тренировочном наборе. Это даст вам идеальную мозаику поверхности (см. Диаграмму ниже).
Чтобы рассчитать VD в R, используйте пакет tripack . Ключевой функцией является voronoi.mosaic, которой вы просто передаете координаты x и y отдельно - необработанные данные, , а не DM - тогда вы можете просто передать voronoi.mosaic в «plot» .
library(tripack)
plot(voronoi.mosaic(runif(100), runif(100), duplicate="remove"))
