поиск совместных алгоритмов

Алексей13 апреля 2005Data Mining1 комментарий

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

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

Также заданы следующие условия.

1.В одной покупке каждый товар может встречаться только однократно.
2.При анализе встречаемости комбинаций количество отпущенного товара не учитывается.
3.При наличии нескольких комбинаций товаров с одинаковой частотой встречаемости необходимо включить в отчет все такие комбинации.

---------

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

Есть еще способ. Завести массив всех товаров, и для каждого товара создать список номеров покупок, в которых он встречался. Потом опять же
из этого списка выбрать все возможные комбинации по 2 и по 3, и посчитать, в скольких покупках они встречались вместе. Этот подсчет вроде
не должен быть очень сложным, так как списки покупок будут изначально отсортированы. Но покупок, по логике, должно быть намного больше, чем
количество продаваемых товаров, => и этот способ не очень нравится.

И последний способ. Можно создать матрицу

товары| A | B | C | D |
-----------------------
A | | | | |
-----------------------
B | | | | |
-----------------------
C | | | | |
-----------------------
D | | | | |
-----------------------

и заполнить ее таким образом, что в ячейке [А,B] будет храниться количество покупок, в которых участвовали А и В. Заполнить несложно, но: 1)
по сложности этот способ, по-моему, не сильно отличается от первого; 2) как разобраться с комбинациями из трех товаров?

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

С уважением,
Алексей Денисов.