Доска почета

Нашел одну статью: K-d дерево строится по следующему правилу: • начальное множество разбивается по значениям векторов в одной из координат, например, по i = 1,…k, на два подмножества; • i выбирается таким образом, чтобы разброс значений по данной координате был максимальным; • разбиение проводится по медиане m, так что одинаковое количество точек оказывается с одной и с другой стороны; • в вершине дерева хранятся значения i , m, разброс значений векторов по каждой координате; • для полученных вершин процесс повторяется. Для поиска n ближайших соседей к вектору q в построенном дереве: • сначала дерево обходится вниз до листа содержащего «ближайшую» к q точку. Эта точка не обязана быть ближайшей, это только первое приближение; • во время спуска по дереву заполняется список поддеревьев, которые еще не обходили. Также запоминаются расстояния до них, которое определяется как минимальное расстояние от точки q до любой точки, находящейся в границах значений поддерева; • из списка выбираем ближайшее к q поддерево и продолжаем поиск в нём; • расстояние до каждого нового найденного претендента сравнивается с радиусом сферы найденных точек с центром в точке q. Если данное расстояние меньше, то точку на сфере заменяем этим претендентом. Алгоритм работает до тех пор, пока в списке есть поддеревья с расстоянием, меньшим радиуса сферы найденных точек.