День добрый. Надеюсь я пишу в правильном разделе.

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

Что нужно:
Нужно найти для одного из пользователей список из других пользователей (к примеру человек 5) у которых имеется похожий набор флажков.

Всё, на что хватило моей фантазии, это генерировать для каждого пользователя некий хеш его флажков... (к примеру если у нас 5 видов флажков и у пользователя есть первый и третий, то его хеш будет: 10100 [1-значит есть, 0-значит нет флажка]). Затем пробегаться по всем пользователям и сравнивать их хеши с текущим пользователем выдавая при этом некую оценку совпадения. За каждое совпадение прибавлять к оценке 1, а за не совпадение отнимать 1. Затем после этого брать 5 пользователей у которых самая большая оценка.

Данное решение дает хороший результат, но очень медлитильно при большом количестве флажков и пользователей.

После небольших размышлений пришел к тому, что можно ускорить поиск жертвуя точностью. К примеру для каждого пользователя можно также сохранять количество имеющихся у него флажков и проверять только тех у кого примерно похожее количество. К примеру если у пользователя 10 флажков, то сверять его хеш только с теми у кого +-3 флажков (т.е. от 7 до 13). Но боюсь, что такой способ поиска сильно ударит по точности. Может кто подскажет как можно улучшить алгоритм не жертвуя при этом точностью? Да и воопще готов выслушать любые варианты реализации.

Раздел правильный. Может, кто и подскажет - но я не буду ;) 

Описана задача, которая сейчас широко востребована, например, в интернет-магазинах и для таргетирования интернет-рекламы, да и вообще в торговле чуть ли не ЛЮБЫМИ товарами и услугами (при широкой номенклатуре предлагаемого товара). "Флажки" есть аналог совершения тех или иных покупок/действий, надо для конкретного пользователя найти ряд других пользователей с аналогичным поведением/предпочтением - посмотрев, какие еще действия и покупки ранее совершали "похожие" пользователи, можно будет предложить текущему эти самые варианты (которыми, предположительно, он заинтересуется с бОльшей вероятностью, чем другим случайно выбранным товаром). 

На подобных задачах я деньги зарабатываю, и называть широкому кругу лиц алгоритмы и где почитать - увольте ;)

Кстати, на русском обзывают такие алгоритмы кучей доморощенных названий, причем калька с формального английского двухсловного названия встречается в рунете всего на 16 страницах и 10 сайтах (пару недель назад смотрел), одна из этих страниц - в википедии, но ещё пустая (а алгоритмы начали активно разрабатываться 15 лет назад, первая же публикация была в 92).

Наверное, стоит сразу внести одно уточнение. Ваша формулировка предполагает две, вообще говоря, существенно разные задачи. 

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

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

Соответственно, для начала определитесь - какую из двух задач Вы решаете.


Хм... как говорится, ничего личного, но я бы в такой ситуации либо поделился бы информацией, либо помолчал.

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

VictorTsaregorodtsev, соглашусь с тов-щем Фантом, если уж не хотите делится никакой информацией, то лучше ничего не писать. Но я был бы признателен, еслиб вы поделились хотябы ссылками на упомянутые 10 сайтов.


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


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

Megas, 
Какое количество пользователей и флажков?



Не обязательно проходить по всем. Пользуйся деревьями.

А вообще я бы загнал в БД и предоставил бы эту работу СУБД она сама прекрасно справиться без вас.

Pavia, флажков сотни, а пользователей сотни тысяч. В принципе эту проблему я и решаю частично с помощью СУБД. Но я не совсем понимаю, как она может мне помочь кроме как предоставить данные в удобочитаемом виде? Если есть идеи по этому поводу, то я использую MySQL.

П.с. не совсем понял причем тут деревья? имхо, они совершенно тут не помагают.

Это сообщение отредактировал(а) Megas - 10.2.2010, 20:08

Megas, посмотри сюда: http://mechanoid.narod.ru/nns/memory/

Возможно этот вид нейронных сетей поможет тебе решить задачу. 

Ну да. Остается найти "места скоплений" получившихся точек и золотой ключик в кармане.

Визуальная картинка:
представим, что у нас 3 разных флага, наличие или отсутствие его будем отмечать 0 или 1. получим вектор, к примеру, у нас есть комплекты флагов (0,1,1) , (1,1,1) и (0,0,0). расстояние между первым и двумя остальными 1 и корень из 2, соответственно. (вспоминаем тригонометрию?). Итого - первый и второй более похожи, чем первый и третий. imho - это уже практически готовое решение..


  

Как вариант. В такой постановке (я вот так и не понял, этого хочет топикстартер или нет) для этой задачи существует много стандартных методов решения. Ключевые слова для поиска в интернете и литературе - "кластерный анализ".

Обдумал идею с многомерным пространством... в целом идея интересная, но если призадуматся, то чтото подобное я и так использую.
Ведь я создаю некий хеш (к примеру: 1010011100...), который можно воспринять как некий тип записи координаты точки в пространстве (где каждая цифра означает координату, а её значение - позиция точки на этой координате). Но в моём случае вычислять близость двух точек гораздо проще, ведь я использую обычное сложение и вычитание (всё описано в первом сообщении), а не корень. Хоть это и дает более грубый результат в плане точности, но работает гораздо быстей.
А я ищу ещё более быстрый вариант.

Это сообщение отредактировал(а) Megas - 14.2.2010, 14:48

Megas, Экономить на корнях? Хм... а откуда флажки-то берутся? Сдается мне. что экономить надо начинать с базы данных .

Для примерчика - разница между хешем 10000000000111 и 00000000000111 должна быть не очень большой, если подключать к этому элементарную логику. А как отнесутся к такому "сложение и вычитание"?

Вообще это глупости. Во-первых просто неверно рассматривать хеш как отображение данных в многомерном пространстве, а сложение вычитание как метрику этого пространства. Это, простите, фигня какая-то  

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