Предполагаем, что схожесть некоторых объектов мы можем вычислить путем вычисления метрики относительно классификации объектов разными классификаторами.
Т.е. у каждого объекта для каждого классификатора имеем своё соответствие.
Вопрос:
как быстро найти n наиболее (или наименее) схожих объектов для объекта X, когда порядок объектов исчисляется десятками миллионов, а классификаторов десятками тысяч?
Если нужно сгруппировать очень большое количество объектов то стоит попробовать создать хеш-функцию для результатов классификатора (такую чтоб она обязательно выдавала одинаковые хешы для объектов предположительно одной группы, но не гарантировала что объекты с одинаковым хешем были в одной группе).
Имея хеш функцию мы уже спокойно можем отсортировать объекты по ее значению даже если все значения хешей не помещаются в оперативную память (можно использовать B-tree например).
А вот уже после сортировки на группы с одинаковыми хешами можно применять более точные алгоритмы чтоб разбить эти группы на искомы подгруппы, так как область поиска будет уже значительно меньше.
Ну смотрите, есть устойчивые сортировки, не меняющие отсортированность по другому признаку. Сортируем по всем, получается что-то типа дерева. Затем сначала выбираем границы записей, подходящих по одному признаку (они рядом будут все), потом ищем в них (уже быстрее, чем искать везде) по другому, и.т.д. Когда критерии закончились — вернули записи в заданных границах.
Хотя это первое что пришло в голову, может есть уже готовые методологии :(
Вопрос не в классификаторах. А то, как на основе их работ в итоге найти схожие объекты. Есть большая матрица — по горизонтали испытуемые объекты, по вертикали классификаторы — а в ячейка номер класса объекта в этом классификаторе.
На основе этой матрицы можно получить входные векторы (соответственно столбцы матрицы) для карты Кохонена, которая среди них выделит кластеры схожих объектов.
Её нужно обучать (точнее сводить). Что делать, когда эти данные активно модифицируются — появляются новые классификаторы или получаем результат для новый связки объект-классификатор?
Спасибо! Похоже на то, что он применим в данном задаче. И схож с моим мыслями. Что набор присвоенные классов для разных классификатор объекта можно считать за координату в w-мерном пространстве (где w — кол-во классификатор). Тогда разбивая все координаты на районы можно уменьшить вычислительную сложность поиска.
