Перейти к содержимому
Compvision.ru
mrgloom

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

Recommended Posts

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

забавно брутфорс на куде работает быстрее всяких специальных структур

http://www.i3s.unice.fr/~debreuve/kNN/

но наверно там ограничение по памяти есть.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

кстати сам не так давно наткнулся на 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.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

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

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

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

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

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

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

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

  • Like 2

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Для каждого кластера строим список из его нескольких ближайших соседей. Чтобы если при "боевой работе" придёт сэмпл с краю кластера - 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/

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

еще 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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

еще метод, но там расстояние хэмминга и бинарные строки.

http://habrahabr.ru/post/211264/

еще для бинарных векторов есть LSH(Locality Sensitive Hashing)

http://stackoverflow.com/questions/12952729/how-to-understand-locality-sensitive-hashing

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

варианты:

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

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×