Welcome to svlab

Member Login

Lost your password?

Not a member yet? Sign Up!

Предыдущий пост
28 Oct 2017

Одним из методов аппроксимации данных сложной топологии является построение древовидных структур. В работе предложен эвристический метод построения древовидного графа на базе метода Верле и физической интерпретации точек данных в многомерном пространстве как центров притяжения. Данный метод построения древовидной структуры протестирован на примере древовидных данных.

Известны несколько способов построения древовидных графов без циклов наилучшим образом аппроксимирующих данные (топологические грамматики, минимизация упругой энергии графа) [Gorban A., 2007, Bach F., 2003]. Древовидный граф представляет собой набор узлов и упругих связей между ними. В качестве таких связей могут выступать пружинная связь между парой точек с равновесным расстоянием между точками и ребра жесткости тройки узлов с равновесным углом между узлами.

Для аппроксимации набора точек древовидной структурой предлагается использовать физическую интерпретацию точек данных как центры притягивающие узлы графа.

Для расчета движения точек древовидного графа в поле притяжения и учета связей между узлами графа предлагается использовать метод численного интегрирования Верле.

Метод Верле – это итерационный метод вычисления следующего местоположения точки по текущему и прошлому местоположениям.  

Численный эксперимент

Работа алгоритма роста графа на базе метода Верле была протестирована на примере древовидных данных (рис. 1).

 

 

 

Рис. 1. Визуализация процесса роста древовидного графа.

 

Программная реализация

Метод Верле был реализован программно с использованием общедоступной JavaScript библиотеки Verlet.js, которая была усовершенствована для многомерного случая. Web приложение для аппроксимации данных на базе метода Верле доступно по адресу http://svlaboratory.org/application/topgrammars после регистрации нового пользователя. Приложение позволяет визуализировать процесс сходимости метода Верле в заданной плоскости координат.

Заключение

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

SHARE:

#

Post dicussion

Контакты

Для связи svbeat@yandex.ru

  • 1
  • 1