Здравствуйте, Sinclair, Вы писали:

S>То, что я помню из университетского курса по матстатистике, намекает что мне придётся прогнать 10^3*10^3 свёрток, чтобы обнаружить попарные корреляции. Выглядит вычислительно громоздким.

Ну, размер полной сетки ассоциаций и так будет n*(n-1)/2?
Т.е., тебе в любом случае именно столько значений надо вычислить.


S>Кроме того, не вполне понятно, как их нормировать, чтобы получить сопоставимые числа.

ИМХО, нормировка тут простая, её коэф — это произведение результатов ФНЧ по каждому товару, либо его среднее арифметическое.

Есть, скажем, серия a₁, a₂, a₃, требуется найти текущее среднее a'.

На каждой покупке, где участвует a_i, делаем так:
a' += (a_i-a')*К, где К — это коэф. ФНЧ первого порядка в пределах 0..1. Чем меньше К, тем плавнее будет фильтрация.

Либо можно вычислять строгое среднее арифметическое на каждом шаге:
a' = (a'*(i-1)+a_i)/i, где i = 1, 2, 3, ... — это номер покупки конкретного a (т.е. серия по кол-ву покупок конкретного товара).
Т.е., для строгого среднего арифметического придется хранить число, показывающее, сколько раз его купили.
С другой стороны, не надо будет хранить число, показывающее, сколько всего его купили, т.к. оно будет равно произведению сохранённого среднего на кол-во раз. ))

В общем, получили среднее по каждому товару, теперь нормируем каждое слагаемое свертки на каждом шаге вычисления:
(ab)_i = (a_i/a')*(b_i/b')

Саму текущую свертку (ab)' тоже вычисляем как накопительное среднее арифметическое.
(ab)' = ((ab)'*j_x+ab_j)/j, где j = 1, 2, 3, ... — это текущий номер покупок вообще, т.е. серия по кол-ву вообще всех покупок, и j_x — это номер последней покупки, в которой выпадала пара ab (для того, чтобы не обновлять (ab)' на каждом шаге).

Только тут стоит учесть, что "последний раз" регистр (ab)' обновлялся тогда, когда последний раз встречалась эта комбинация, поэтому, если требуется посмотреть текущую "аналитику", то перед её выдачей надо сделать "фиктивную покупку" по всем парам товаров ab, т.е., грубо для отображения взять некий (ab)'', где:
(ab)'' = (ab)''*j_x/j, где взять текущее значение номера всех покупок j.

==========
Пара соображений.

ИМХО, ФНЧ может быть чуть лучше, чем строгое среднее арифметическое для нормировки, т.к. даёт результат в динамике, т.е. подстраивается под текущую коньюктуру. Помимо этого для ФНЧ не надо по каждому продукту хранить кол-во покупок i, где i может быть в итоге достаточно большим и начать вносить погрешность при вычислении строгого среднего арифметического на каждом шаге. В этом смысле вычисления ФНЧ будут точнее, начиная от того момент, когда К будет больше, чем значений 1/i.

Что касается коэф ФНЧ 1-го порядка, то там такая формула:
— время 3*Тау даёт ~95% "устаканивания" процесса;
— т.е. для "устаканивания", скажем, на выборке из 3000 элементов К будет равен 1/1000.

Итого, уже от 1000-го элемента вычисления ФНЧ будут становиться сравними по точности со "строгим" средним арифметическим, и чем дальше, тем точнее. Для ФНЧ 1-го порядка обычного float32 хватает за глаза для приличной точности.

А вот для вычисления (ab)' способ ФНЧ уже не подойдёт, т.к. ФНЧ должно работать на каждом шаге, но в предложенных вычислениях обновление (ab)' происходит только тогда, когда встречается эта пара. Поэтому, вычисления (ab)' стоит делать с двойной точностью.

S>Может быть, есть какой-то более оптимальный способ обнаружить закономерности, не выписывая отдельные единичные гипотезы с конкретными номерами продуктов?

Ну, тебе всё-равно по каждому входному числу a_i, b_i, c_i и т.д. необходимо будет произвести какие-то вычисления.
ИМХО, вычисления свертки в "лоб" — простейшие.
Даже по историческим данным.
А уж если затем делать их в процессе самих покупок — то совсем бесплатно, считай.

Здравствуйте, Sinclair, Вы писали:

S>То, что я помню из университетского курса по матстатистике, намекает что мне придётся прогнать 10^3*10^3 свёрток, чтобы обнаружить попарные корреляции. Выглядит вычислительно громоздким.

Ну, размер полной сетки ассоциаций и так будет n*(n-1)/2?
Т.е., тебе в любом случае именно столько значений надо вычислить.


S>Кроме того, не вполне понятно, как их нормировать, чтобы получить сопоставимые числа.

ИМХО, нормировка тут простая, её коэф — это произведение результатов ФНЧ по каждому товару, либо его среднее арифметическое.

Есть, скажем, серия a₁, a₂, a₃, требуется найти текущее среднее a'.

На каждой покупке, где участвует a_i, делаем так:
a' += (a_i-a')*К, где К — это коэф. ФНЧ первого порядка в пределах 0..1. Чем меньше К, тем плавнее будет фильтрация.

Либо можно вычислять строгое среднее арифметическое на каждом шаге:
a' = (a'*(i-1)+a_i)/i, где i = 1, 2, 3, ... — это номер покупки конкретного a (т.е. серия по кол-ву покупок конкретного товара).
Т.е., для строгого среднего арифметического придется хранить число, показывающее, сколько раз его купили.
С другой стороны, не надо будет хранить число, показывающее, сколько всего его купили, т.к. оно будет равно произведению сохранённого среднего на кол-во раз. ))

В общем, получили среднее по каждому товару, теперь нормируем каждое слагаемое свертки на каждом шаге вычисления:
(ab)_i = (a_i/a')*(b_i/b')

Саму текущую свертку (ab)' тоже вычисляем как накопительное среднее арифметическое.
(ab)' = ((ab)'*j_x+ab_j)/j, где j = 1, 2, 3, ... — это текущий номер покупок вообще, т.е. серия по кол-ву вообще всех покупок, и j_x — это номер последней покупки, в которой выпадала пара ab (для того, чтобы не обновлять (ab)' на каждом шаге).

Только тут стоит учесть, что "последний раз" регистр (ab)' обновлялся тогда, когда последний раз встречалась эта комбинация, поэтому, если требуется посмотреть текущую "аналитику", то перед её выдачей надо сделать "фиктивную покупку" по всем парам товаров ab, т.е., грубо для отображения взять некий (ab)", где:
(ab)" = (ab)'*j_x/j, где взять текущее значение номера всех покупок j.

==========
Пара соображений.

ИМХО, ФНЧ может быть чуть лучше, чем строгое среднее арифметическое для нормировки, т.к. даёт результат в динамике, т.е. подстраивается под текущую коньюктуру. Помимо этого для ФНЧ не надо по каждому продукту хранить кол-во покупок i, где i может быть в итоге достаточно большим и начать вносить погрешность при вычислении строгого среднего арифметического на каждом шаге. В этом смысле вычисления ФНЧ будут точнее, начиная от того момент, когда К будет больше, чем значений 1/i.

Что касается коэф ФНЧ 1-го порядка, то там такая формула:
— время 3*Тау даёт ~95% "устаканивания" процесса;
— т.е. для "устаканивания", скажем, на выборке из 3000 элементов К будет равен 1/1000.

Итого, уже от 1000-го элемента вычисления ФНЧ будут становиться сравними по точности со "строгим" средним арифметическим, и чем дальше, тем точнее. Для ФНЧ 1-го порядка обычного float32 хватает за глаза для приличной точности.

А вот для вычисления (ab)' способ ФНЧ уже не подойдёт, т.к. ФНЧ должно работать на каждом шаге, но в предложенных вычислениях обновление (ab)' происходит только тогда, когда встречается эта пара. Поэтому, вычисления (ab)' стоит делать с двойной точностью.

S>Может быть, есть какой-то более оптимальный способ обнаружить закономерности, не выписывая отдельные единичные гипотезы с конкретными номерами продуктов?

Ну, тебе всё-равно по каждому входному числу a_i, b_i, c_i и т.д. необходимо будет произвести какие-то вычисления.
ИМХО, вычисления свертки в "лоб" — простейшие.
Даже по историческим данным.
А уж если затем делать их в процессе самих покупок — то совсем бесплатно, считай.