Jump to content
Compvision.ru
Sign in to follow this  
mrgloom

knn не загружая всего в память?

Recommended Posts

возможно ли делать как то поиск ближайших K соседей не загружая все семплы в память?

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

или вообще как то поставить лимит по использованию памяти, возможно это должно быть несколько деревьев? т.е. из всей выборки формируем несколько деревьев такого размера, чтобы помещались в память и при поиске ищем в каждом дереве отдельно, потом всё это дело скидываем в 1 массив и опять там находим ближайщие k.

Share this post


Link to post
Share on other sites

Я думаю что вполне возможно разбить деревья на фрагменты.

Для каждого фрагмента должен быть один корень и несколько выходов.

Получаются такие макроузлы, каждый из которых представляет собой дерево.

Share this post


Link to post
Share on other sites

>возможно ли делать как то поиск ближайших K соседей не загружая все семплы в память?

Я бы сначала раскластеризовал (или заквантовал - если кластеров в данных нет) данные методом динамических ядер на достаточно большое число кластеров/квантов, а knn запускал только для того кластера, к которому относится точка, и для нескольких смежных кластеров.

Если данных куча (сотни тысяч) - динамические ядра в онлайн-режиме коррекции за достаточно малое число итераций хорошо устаканиваются. Т.е. десяток-другой прокруток всей выборки (для кластеризации) - а потом работай внутри отдельных кластеров. Я бы для этого ещё и выборку переписал в другом порядке (сэмплы одного кластера идут друг за другом) - чтобы винт читал длинные последовательные блоки данных (кластеры целиком), а не бегал взад-вперёд то за одним, то за другим сэмплом

Share this post


Link to post
Share on other sites

Ну допустим кластеризовал я данные на кластеры определенного размера, потом что? центры кластеров в дерево?

и что такое "динамические ядра" ?

кстати сам не так давно наткнулся на Vector Quantization

но сложилось впечатление, что это нужно для того, чтобы например есть у нас векторы разной длины(например на разных изображениях было найдено разное кол-во особых точек SIFT) и мы чтобы подать на классификатор(вектора для всех изображений должны быть одной длины) должны либо гистограмму построить, либо например кластеризовать на заданное кол-во кластеров и получить вектор из центра кластеров.

k-means это вроде частный случай Vector Quantization, хотя я может не правильно понял о чем Vector Quantization.

еще вопрос как сделать такой поиск для гистограмм?

или по большому счёту гистограмма представима как вектор и всё тоже самое.

опять же не знаю какой тут они алгоритм используют (kd-trees and box-decomposition trees)

но там написано

Why approximate nearest neighbors?

Computing exact nearest neighbors in dimensions much higher than 8 seems to be a very difficult task. Few methods seem to be significantly better than a brute-force computation of all distances. However, it has been shown that by computing nearest neighbors approximately, it is possible to achieve significantly faster running times (on the order of 10's to 100's) often with a relatively small actual errors. ANN allows the user to specify a maximum approximation error bound, thus allowing the user to control the tradeoff between accuracy and running time.

Share this post


Link to post
Share on other sites

Динамические ядра - это идущий из СССРовских времён синоним k-means

Ну и переформулирую прошлый пост на ином языке.

1) У Вас есть N сэмплов

2) Кластеризуем их - получаем n кластеров, n<<N. Кластеризовать я советую онлайновым алгоритмом.

3) Для каждого кластера строим список из его нескольких ближайших соседей. Чтобы если при "боевой работе" придёт сэмпл с краю кластера - knn работал и с примерами соседнего кластера.

Начинаем боевую работу

1) Приходит сэмпл - определяем, в какой кластер он попадает. Затрат - n вычислений длин векторов разностей.

2) Думаем - а не нужно ли взять какие-то соседние кластеры? Например, те, расстояние от сэмпла до центра которых сопоставимо с расстоянием от сэмпла до его кластера. В общем, тут можно придумать эмпирику, ради экономии вычислений берущую соседей только при достаточном удалении сэмпла от центра его кластера.

3) На сэмплах кластера (и, при необходимости, сэмплах его соседях) запускаем knn. Число примеров в этом одном или нескольких кластерах будет в разы меньше, чем N - во столько же раз и ускорится knn.

Т.е. через пару-тройку десятков классификаций сэмплов - компенсируем время, затраченное на предварительную кластеризацию, и затем начинаем работать в плюс (по сравнению с постоянным запуском knn по всем N сэмплам)

  • Like 2

Share this post


Link to post
Share on other sites
Для каждого кластера строим список из его нескольких ближайших соседей. Чтобы если при "боевой работе" придёт сэмпл с краю кластера - knn работал и с примерами соседнего кластера.

для каждого кластера список ближайших кластеров?

каков критерий? брать k ближайших кластеров?

Приходит сэмпл - определяем, в какой кластер он попадает. Затрат - n вычислений длин векторов разностей.

по идее можно ведь и дерево сделать для n и искать быстрее.

тут плюс этого метода только в том, что можно от N перейти к n, заранее зная память под это дело, а каждый отдельный кластер опять же можно хранить на диске + информация в виде дерева(тоже на диске) и таких уровней можно сделать наверно не 2, а сколько требуется.

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

еще неплохо было бы подумать как всё это можно проапдейтить при добавлении новых данных.

http://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

еще похоже на Voronoi Tessellation

а вообще еще вот по large scale nearest neighbor/large scale image search

http://www.cs.cmu.edu/~epxing/Class/10701/reading/icmr2011_nvtree.pdf

http://csce.uark.edu/~jgauch/library/Video-Retrieval/Lejsek.2009.pdf

http://hal.inria.fr/docs/00/79/64/75/PDF/icmr115-moise.pdf

caltech large scale image search toolbox (жаль что под лин)

https://code.google.com/p/caltech-image-search/

Share this post


Link to post
Share on other sites

еще 1 идея как не хранить доп. информацию о центре кластера

The standard knn classifier implemented using a balltree. A balltree algorithm efficient on high dimensional attributes is used. The balltree algorithm does not calculate a center for the balls and instead efficiently indentifies the best(approximately) datapoint that can be used as the center. This saves a lot of memory required for the tree.

идея отсюда

https://www.autonlab.org/autonweb/16478.html

Share this post


Link to post
Share on other sites

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

варианты:

1. на основании набора векторов, по каждой ячейке(числовой позиции например вектор vec={2 3 7} 3 позиции) вычислять среднее или медиану и соответственно если больше то 1, если меньше то 0.

2. кластеризовать вектора, взять k центров и смотреть расстояние до центров, если меньше dist то 1, если больше то 0 (соответственно тут мы получим сокращение размерности). непонятно правда как выбирать k и dist, в предельных случаях будем иметь пустой или очень разреженный вектор или всё в единицах ,а можно сначала заполнить новые вектора длины k расстояниями dist и сделать как в пункте 1.

п.с. это похоже получается хэш-функция?

но если так делать, то уже точное соответствие не найдешь, т.к. потеря информации.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×