Как индексировать последовательности поплавков? (для эвклидовой дистанции)

-1

ОБНОВЛЕНИЕ 1: речь идет не о простой сортировке списков поплавков, а в способе индексации списков поплавков, чтобы позже можно было быстро найти те, у которых были близкие евклидовы расстояния до образца.Как индексировать последовательности поплавков? (для эвклидовой дистанции)

ОБНОВЛЕНИЕ 2: Это нормально, если это другой метод, чем просто индекс поплавка. Основная цель - быстро найти похожие (короткие евклидова расстояния) последовательности без необходимости читать целую или большую часть базы данных последовательностей.

Возможно, вычисление среднего достаточно, но то, что я ищу, является числом с плавающей точкой, которое может быть описательным для последовательности, которую она представляет.

Например, эти последовательности поплавков:

sequence[0] = [0.42, 0.81, 0.33, 0.19, 0.56] 
sequence[1] = [0.72, 0.93, 0.14, 0.92, 0.88] 

average[0] = 0.462 
average[1] = 0.718

Идея заключается в том, чтобы отсортировать последовательности с помощью этого «индексации поплавком» (в данном примере: среднее), так что, когда другая последовательность сравнивается со списком последовательности, чтобы найти похожие, он может начать сравнивать (эвклидовое расстояние) от ближайшего «индексационного поплавка» и перемещать указатель вверх и вниз от этой точки массива.

Это будет число с плавающей точкой, которое позволит «приблизиться» к тем последовательностям, которые имеют меньшие евклидовы расстояния до поисковой последовательности.

источник

2014-10-23 Davinish

Язык: Python. – Davinish

Вам нужно использовать только один float для вашего индекса, или вы можете использовать более сложную структуру данных? В принципе, в высокоразмерном пространстве, таком как ваше, одно плавание не будет хорошо тарифицироваться. Вы можете лучше использовать эвклидовую норму (квадратный корень из суммы квадратов элементов), которая будет группировать элементы одинаковой величины вместе, но, вероятно, не поможет слишком много, когда данные станут большими. Если количество последовательностей очень велико, вы захотите использовать структуру данных, такую как kd-tree (не так сложно писать), чтобы быстро найти соседей. – Gretchen

Это нормально, если это сложнее. Цель состоит в том, чтобы быстро находить последовательности в больших списках без необходимости считывать все (или слишком много) базы данных. – Davinish

f.e. в C# вы можете использовать отсортированный словарь http://msdn.microsoft.com/de-de/library/f7fta44c(v=vs.110).aspx

В основном вы можете реализовать структуру данных самостоятельно на каждом языке.

источник

2014-10-23 08:49:32 Anzzi

, если это простой вид списков поплавков, это другое. Идея состоит в том, чтобы индексировать последовательности для приближения в списке тех, у кого есть аналогичное евклидово расстояние. Это будет первый шаг, а затем, при поиске последовательности, начните поиск на тех, у кого есть похожий индекс, и, таким образом, быстрее найти похожие последовательности. – Davinish

Я не уверен, правильно ли понимаю ваш вопрос.

Но это звучит так, как будто вы ищете R-дерево, R * -tree, kd-tree, тип данных типа quadtree? То есть индексировать структуры для поиска ближайших соседей?

источник

2014-10-23 18:46:58

Возможно. Идея состоит в том, чтобы индексировать последовательности, чтобы быстро найти ближайших соседей, т. Е. Кратчайшее эвклидово расстояние. Хотя не только ближайшие, но и несколько близких с порогом. – Davinish

Да, эти структуры данных могут ускорить и поиск kNN. –

Как индексировать последовательности поплавков? (для эвклидовой дистанции)

ответ

Смежные вопросы