Какие существуют алгоритмы поиска оптимальной выборки/среза?

Question

[ifaceman]

Приветствую всех!

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

На каждого пользователя также имеется некая статистика (например - кол-во входов в систему в месяц).
Соответственно, по любым сочетаниям параметров можно составить среднюю статистику (например: пол+возраст, пол+возраст+семейное_положение, ...+...+*) - мужчины 30 лет входили в систему в среднем 32 раза в месяц. Таким образом формируется срез.

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

Answer 1

[Андрей]

k-Nearest Neighbours (kNN)
Ваша задача в терминах этого алгоритма соответствует вопросам :
1) как настроить веса (значимость) влияния параметров на расстояние между соседями
2) какое ядро выбрать
3) как определить оптимальное k для этого ядра
На все три есть конкретные ответы в виде алгоритмов - литературы очень много.

Answer 2

[Андрей Вершинин]

Регрессионный анализ

Comments

[ifaceman]

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

[Андрей Вершинин]

@ifaceman Если это не то, тогда я немного не понимаю, что вам нужно. Мы имеем данные о конкретном пользователе, набор срезов данных по разным критериям, и нужно подобрать тот срез, который будет больше всего "подходить"?

[ifaceman]

@WolfdalE Срезы можно заранее сформировать, но смысла нету.
Зашел, например, человек, у которого заполнено мужчина+18 лет+менеджер+....
Начинаем перебор срезов:
-мужчина(220 человек в срезе, низший приоритет, т.к. всего один совпадающий параметр)
-18 лет(...)
-мужчина+18 лет(...)
...
Для каждого среза считаем определенный коэффициент, зависящий от числа человек в срезе и числа его параметров, совпадающих с нашим пользователем. По нему определяем, какой срез брать.

Существует что-то похожее?

[Андрей Вершинин]

@ifaceman Я думаю, нет смысла что-то искать, т.к. всё просто: пусть каждый параметр будет иметь свой весовой коэффициент (если все равнозначны, то каждый параметр будет иметь вес 1 / K, где K - кол-во параметров). Количество человек в срезе будет влиять таким образом: в спорных ситуациях (когда у одного среза вес выше, чем у второго, а кол-во людей меньше) будем считать отношение меньшего кол-ва к большему (получим значение в (0; 1)). Затем возьмем отношение большего веса к меньшему, получим значение в пределах (1, +inf). Перемножив эти два числа, получим другое число, которое будем сравнивать с единицей: если больше либо равно, то берем тот срез, у которого больше вес, в другом случае - в который входит больше людей.

[ifaceman]

@WolfdalE Идея понятна, спасибо!
А насколько это быстро будет работать при больших БД, множестве параметров и большой статистике?
Если пользователь делает запрос на загрузку страницы с товарами, а система выдаст ему наилучшие товары по его срезу. Сколько времени это займет?

[Андрей Вершинин]

@ifaceman Это зависит от количества срезов. Для человека, загружающего страницу, это будет незаметно.