Корреляции и классификации
От: Sinclair Россия https://github.com/evilguest/
Дата: 21.03.17 10:27
Оценка:
Всем привет,
К сожалению не обучался нужным курсам, поэтому слабо знаком с терминологией. Бодрое гугление по википедии показало, что как обычно — надо знать половину ответа, чтобы получить вторую.

В общем, картина вот какая:
Есть, допустим, порядка 10^3 разных продуктов.
Их могут покупать в более-менее произвольных сочетаниях.
Допустим, у нас есть данные о примерно 10^5 покупок. Каждая покупка — это вектор из тех самых 10^3 ячеек, где каждая соответствует количеству купленного продукта номер i. (у нас это количество — всегда целое, но это не так важно).
Естественно, большинство значений в таком векторе равно нулю. Там очень быстро спадает "хвост" распределения: 1 продукт покупает 99% потребителей, 2 продукта — 0.9% или 90% из оставшихся, 3 продукта — 0.09%, 4 и более — следовые количества покупока.

И вот теперь у нас есть желание посмотреть на корреляции между продажами различных продуктов.
Ну, то есть у нас есть гипотезы типа "покупатели продукта X часто покупают продукт Y", или "покупатели продукта X1 никогда не покупают продукт X2".
Хуже того, могут быть всякие закономерности "объём покупки продукта Y хорошо коррелирует с суммой объёмов покупки X1 и X2"
То, что я помню из университетского курса по матстатистике, намекает что мне придётся прогнать 10^3*10^3 свёрток, чтобы обнаружить попарные корреляции. Выглядит вычислительно громоздким.
Кроме того, не вполне понятно, как их нормировать, чтобы получить сопоставимые числа.

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

Где можно почитать о решении таких задач?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Корреляции и классификации
От: Mazay Россия  
Дата: 21.03.17 10:43
Оценка: 14 (1)
Здравствуйте, Sinclair, Вы писали:

Сначала сделай анализ главных компонент.
Продукты, которые линейно коррелируют между собой, будут засунуты в одну компоненту.

Потом посмотри на анализ независимых компонент — выделишь типы покупателей, насколько я понимаю.
Главное гармония ...
Re: Корреляции и классификации
От: NotImplemented США github.com/NotImplemented
Дата: 21.03.17 13:32
Оценка: 70 (1)
Здравствуйте, Sinclair, Вы писали:

S>Где можно почитать о решении таких задач?


Рекомендую следующий курс по statistical learning и книгу The Elements of Statistical Learning.

Можете посчитать матрицу корреляции с помощью BLAS, например, реализация на R или на питоне numpy.corrcoef.
Метод главных компонент также требует построения матрицы ковариаций.
Отредактировано 21.03.2017 14:02 NotImplemented . Предыдущая версия . Еще …
Отредактировано 21.03.2017 13:37 NotImplemented . Предыдущая версия .
statistical learning
Re: Корреляции и классификации
От: Code Digger Грузия  
Дата: 21.03.17 13:48
Оценка: 119 (2)
Здравствуйте, Sinclair, Вы писали:

S>Всем привет,

S>К сожалению не обучался нужным курсам, поэтому слабо знаком с терминологией. Бодрое гугление по википедии показало, что как обычно — надо знать половину ответа, чтобы получить вторую.

S>В общем, картина вот какая:

S>Есть, допустим, порядка 10^3 разных продуктов.
S>Их могут покупать в более-менее произвольных сочетаниях.
S>Допустим, у нас есть данные о примерно 10^5 покупок. Каждая покупка — это вектор из тех самых 10^3 ячеек, где каждая соответствует количеству купленного продукта номер i. (у нас это количество — всегда целое, но это не так важно).
S>Естественно, большинство значений в таком векторе равно нулю. Там очень быстро спадает "хвост" распределения: 1 продукт покупает 99% потребителей, 2 продукта — 0.9% или 90% из оставшихся, 3 продукта — 0.09%, 4 и более — следовые количества покупока.

S>И вот теперь у нас есть желание посмотреть на корреляции между продажами различных продуктов.

S>Ну, то есть у нас есть гипотезы типа "покупатели продукта X часто покупают продукт Y", или "покупатели продукта X1 никогда не покупают продукт X2".
S>Хуже того, могут быть всякие закономерности "объём покупки продукта Y хорошо коррелирует с суммой объёмов покупки X1 и X2"
S>То, что я помню из университетского курса по матстатистике, намекает что мне придётся прогнать 10^3*10^3 свёрток, чтобы обнаружить попарные корреляции. Выглядит вычислительно громоздким.
S>Кроме того, не вполне понятно, как их нормировать, чтобы получить сопоставимые числа.

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


S>Где можно почитать о решении таких задач?


Судя по описанию, вам нужен https://en.wikipedia.org/wiki/Association_rule_learning
Скорее всего, он есть во всех хороших ML библиотеках.
В наш век Big Data 10^3 и 10^5 никого уже не впечатляют. :-D
Re: Корреляции и классификации
От: De-Bill  
Дата: 24.03.17 03:49
Оценка: 14 (1)
Частично решается анализом ассоциаций и "market basket analysis".
Как это реализовано в продуктах для DM
http://www2.sas.com/proceedings/forum2007/132-2007.pdf
http://paginas.fe.up.pt/~ec/files_1112/week_04_Association.pdf
Re: Корреляции и классификации
От: vdimas Россия  
Дата: 01.04.17 13:22
Оценка:
Здравствуйте, Sinclair, Вы писали:

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


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


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


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

Есть, скажем, серия a1, a2, a3, требуется найти текущее среднее a'.

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

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

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

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

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

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

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

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

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

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

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


Ну, тебе всё-равно по каждому входному числу ai, bi, ci и т.д. необходимо будет произвести какие-то вычисления.
ИМХО, вычисления свертки в "лоб" — простейшие.
Даже по историческим данным.
А уж если затем делать их в процессе самих покупок — то совсем бесплатно, считай.
Отредактировано 01.04.2017 13:42 vdimas . Предыдущая версия . Еще …
Отредактировано 01.04.2017 13:35 vdimas . Предыдущая версия .
Отредактировано 01.04.2017 13:29 vdimas . Предыдущая версия .
Отредактировано 01.04.2017 13:24 vdimas . Предыдущая версия .
Re: Корреляции и классификации
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 08.04.17 10:55
Оценка: 96 (1)
Здравствуйте, Sinclair, Вы писали:

S>Где можно почитать о решении таких задач?


http://www.daxpatterns.com/basket-analysis/ тут например.
Делается в экселе за полчаса.
Re: Корреляции и классификации
От: Spinifex Россия https://architecture-cleaning.ru/
Дата: 02.05.17 12:43
Оценка: 14 (1)
Все правильно выше написали это market basket analysis. Проще всего познакомиться с алгоритмом apriori. Там используется идея, что есть у вас в вашем примере, предположим продукты A, B, C. Таким образом частота покупок комбинации продуктов AB не может быть выше, чем частота покупки этих продуктов по отдельности. Таким образом можно легко отсечь кучу вычислений.
Алгоритм Apriori
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.