Алгоритм поиска схожих объектов?

Question

[miolini]

Здравствуйте!


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


Т.е. у каждого объекта для каждого классификатора имеем своё соответствие.


Вопрос:


как быстро найти n наиболее (или наименее) схожих объектов для объекта X, когда порядок объектов исчисляется десятками миллионов, а классификаторов десятками тысяч?

Answer 1

[vgrichina]

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

Имея хеш функцию мы уже спокойно можем отсортировать объекты по ее значению даже если все значения хешей не помещаются в оперативную память (можно использовать B-tree например).

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

Answer 2

[Vas3K]

Отсортировать и сгруппировать по критериям. MapReduce.

Comments

[Vas3K]

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

[miolini]

Отсортировать по какому признаку? И как именно раздробить поиск?

[Vas3K]

Ну смотрите, есть устойчивые сортировки, не меняющие отсортированность по другому признаку. Сортируем по всем, получается что-то типа дерева. Затем сначала выбираем границы записей, подходящих по одному признаку (они рядом будут все), потом ищем в них (уже быстрее, чем искать везде) по другому, и.т.д. Когда критерии закончились — вернули записи в заданных границах.

Хотя это первое что пришло в голову, может есть уже готовые методологии :(

Answer 3

[Сергей]

Может попробовать использовать самоорганизующуюся карту Кохонена?

Comments

[miolini]

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

[Сергей]

На основе этой матрицы можно получить входные векторы (соответственно столбцы матрицы) для карты Кохонена, которая среди них выделит кластеры схожих объектов.

[miolini]

Её нужно обучать (точнее сводить). Что делать, когда эти данные активно модифицируются — появляются новые классификаторы или получаем результат для новый связки объект-классификатор?

Answer 4

[Ололёша Ололоев]

Я бы использовал кластерный анализ для этого. Алгоритм ФОРЕЛЬ работает достаточно быстро, можно посмотреть в его сторону.

Comments

[Ололёша Ололоев]

ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81%D0%B5%D0%BC%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%B0_FOREL вот про алгоритм на википедии. У меня где-то должна быть его реализация на делфи.

[miolini]

Спасибо! Похоже на то, что он применим в данном задаче. И схож с моим мыслями. Что набор присвоенные классов для разных классификатор объекта можно считать за координату в w-мерном пространстве (где w — кол-во классификатор). Тогда разбивая все координаты на районы можно уменьшить вычислительную сложность поиска.

[miolini]

Простите за орфографию — увлечён.