Inventor: анализ совместных продаж / кластерный анализ : Закупщик

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

Валера, привет!
1. А как ты видишь методику (алгоритм) выделения кластеров?
2. Что даст выделение этих кластеров? Классификацию?

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



Я приблизительно понимаю, что должно получиться, но не могу понять как это алгоритмизировать.
Быть может нам нужно перебором найти такую пару товаров, которая имеет наибольший коэффициент совместности с анализируемой парой... А вдруг с этой парой другая пара имеет больший коэффициент... Короче нужно просчитывать всю матрицу, если я в том направлении думаю. А потом в этой матрице анализировать неким образом какие пары с какими имеют наибольшую совместность. Пока мои рассуждения меня не особо радуют.
Этот метод анализа реализован в SPSS. Я не пользуюсь этой программой и прокомментировать этого не могу. Вопрос еще вот в чем: сколько времени займет такой анализ, если проводить его в Excel на обычном компьютере? Стоит ли изобретать велосипед, если это уже есть в другой общедоступной программе в базовой комплектации?

Готов пожертвовать свой ПК на благо науки! :D

Ну, в данном примере мы получим сегментирование клиентов. И сможем соответственно анализировать динамику этих сегментов, и понимать, что нужно что-то делать в проблемном сегменте. Или понять, что у нас сейчас совсем не то позиционирование - например мы себя подаём, как VIP, а у нас нет товаров для этих VIP в некоторых категориях.

Да, ты понял всё совершенно точно, и даже навёл меня на мысль, как должен выглядеть алгоритм! - До этого представлял его себе очень смутно.

Смотри, ты считаешь за 5 секунд все пары, потом выбираешь одну с наибольшим значением, и обзываешь это дело первым кластером: заменяешь обе позиции на "1", и где-то запоминаешь, что в первый кластер входят эти две позиции. Дальше повторяешь расчёт, где эти позиции уже являются одной - "1". Соответственно, у тебя возможны две ситуации: либо две других позиции уже образуют кластер - его именуем по аналогии "2", и продолжаем расчёт; либо сильней всего какая-то позиция связана с кластером "1" - тогда ты эту позицию добавляешь в этот кластер - переименовываешь в "1" и "запоминаешь", что она туда входит. Если на каком-то из шагов, окажется, что сильнее всего связаны кластер "24" и кластер "96", то мы все позиции из них объединяем в новый кластер "514" - и далее рассматриваем как единый кластер, при этом в конце расчёта, если нам понадобится опуститься на уровень детализации тех кластеров, мы сможем посмотреть, какие позиции кластера "514" из кластера "24", а какие из "96" - либо будем рассматривать их как нечто единое, в любом случае - это уже делает человек смотря на итоговый результат. Заканчивать работу по кластеризации можно по достижению какого-то коэффициента связности - например, если максимальный коэффициент пары позиций или кластеров меньше 0,7, то заканчиваем расчёт.

По времени, вроде, должно не так долго считаться - конечно всё зависит от заданного критического уровня, когда прервётся расчёт, и количества позиций, но оно во время расчёта будет всё время уменьшаться за счёт их объединения в кластера. Ещё можно попробовать ускорить расчёт за счёт того, что объединять в кластера быстрее - не по одной паре, а сразу все, удовлетворяющие условию "больше 0,7" - тогда ряд количества проверяемых связей будет сходится значительно быстрее и общее время расчёта ощутимо уменьшится...

Ну это решать тебе! Просто, у тебя ядро расчёта уже реализовано, - по сути осталось только его запустить в определённой последовательности N раз... ;)

Так, Валера, давай по порядку :)
- за 5 секунд делается анализ по отдельной позиции, а нам нужно провести тотальный анализ массива, это занимает по тестам Вадима часы. Я правильно думаю, что производиться должен анализ именно всего массива а не одной позиции? Все дальнейшие рассуждение построены на этой основе.
- сделав тотальный анализ массива на предмет совместных продаж мы получаем список пар товаров, продающихся вместе с заданными параметрами. Затем, мы заменяем в этом списке пары товара на номера кластеров. Каждая пара товаров - отдельный кластер, но если какая-то позиция из пары уже входит в другой кластер, то вторую позицию этой пары тоже включаем в этот кластер (если список будет изначально отсортирован в порядке убывания коэффициента совместности, то, думаю, ошибки в этом нет).
- запоминаем какие позиции в какие кластера входят (запоминаем в массив из трех полей: товар, уровень кластеризации, номер кластера) и после этого меняем в исходном массиве (изначальном массиве с номерами документов) наименование номенклатуры на номера полученных кластеров. Запускаем тотальный анализ массива повторно.
- получаем новый результат в виде списка пар товаров, продающихся вместе с заданными параметрами. Можно ли утверждать, что в этом списке будут все номера кластеров, полученные на предыдущем этапе (кажется, что это так, но есть сомнения)? Анализируем полученный список пар по строкам: 1ый цикл по всему списку: если с номером кластера встречается позиция номенклатуры, то мы включаем ее в этот кластер (при этом уровень кластеризации = 1), если в одной из следующих строк встречаем эту же позицию, но в паре с другим кластером, то игнорируем эту строку (вроде бы так...); 2ой цикл по всему списку: анализируем только те строки где встречаются разные кластеры и переименовываем эти кластеры в кластеры второго уровня (если один кластер из пары уже входит в другой кластер второго уровня, то второй кластер из пары включаем в этот же кластер второго уровня), и запоминаем это с уровнем кластеризации = 2.
- после этого меняем в исходном массиве (массиве с номерами документов, откорректированном на 1ом этапе) наименование номенклатуры на номера полученных кластеров и номера кластеров на номера кластеров высшего уровня. Вот тут вопрос: нужно ли делать исправления кластеров на кластера второго уровня, ведь мы включили в имеющиеся кластеры новые позиции и при повторном тотальном анализе массива к этим кластерам могут присоединиться новые позиции номенклатуры? При таком раскладе позиции будут прикрепляться к более большим кластерам верхнего уровня, что лишает нас информации о том, в какой кластер более низкого уровня входит данная позиция.
- так делаем до тех пор, пока выполняется заданный коэффициент совместности между кластерами. По идее в итого получим один кластер самого высокого уровня - весь наш ассортимент.
- в итоге, массив (в который мы запоминали какой товар соответствует какому кластеру, и какому кластеру более высокого уровня какие кластеры соответствуют более низкого уровня) можно представить в виде сводной таблицы, приблизительно такого вида:



По идее весь этот анализ в зависимости от количества уровней кластеризации будет проходить во сколько-то раз дольше обычного тотального анализа совместных продаж. Вот во сколько, пока не знаю =) Расскажи подробнее, что ты имел ввиду тут: "объединять в кластера быстрее - не по одной паре, а сразу все, удовлетворяющие условию"? Это соответствует моим рассуждениям выше?

Вот как раз вопрос как это сделать и не слишком ли большое значение у N ;)

Вообще, идея сильная. Если это все реализовать, то ... круто, короче, это все )

Да, тогда придётся тратить много времени...

Никаких ошибок. Только я бы ещё сортировал по второму параметру - количеству документов из которых получено значение. То есть, для пар с одинаковыми коэффициентами мы будем сначала объединять те, которые чаще в абсолютных цифрах продавались друг с другом.

Да, только для ускорения работы, нужно убрать лишние записи - ведь почти в каждом документе теперь будут по две "одинаковых" позиции (из одного кластера).

У меня сомнений не возникает - им, просто, некуда деваться... :) "Ты в ритме танца, тебе некуда деваться!" (с) "Дискотека Авария"

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

Да, в этом-то весь и смысл.

Ну, я думал, что эта информация будет запоминаться в отдельном списке со всеми изначальными позциями.

Совершенно верно, ну и может ещё останутся позиции, которые не покупают ни с чем - тоже интересный результат.

Да, это было бы - супер!

Ага.

Ну, да - в конце концов, будет народ на выходные оставлять считаться. Или на новогодние праздники - особо часто проводить такой анализ всё равно не надо. ;)

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

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

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

Скорость будет напрямую зависеть от скорости уменьшения количества уникальных строк (в связи с удалением дубликатов) в исходном массиве. Вот чисто с потолка интуитивно, думаю что будет раз в 5 дольше идти анализ, чем простой тотальный (заметьте, тотальный анализ охрененного массива на совместные продажи мы уже называем простым!) анализ совместных продаж. Т.е. в случае Вадима это займет на 700 тыс. строк 2-3 суток. Пусть Excel работает за вас, а вы покурите :D

Мое предложение в силе - готов пожертвовать ПК :D

Начал писать код для кластерного анализа, столкнулся с интересными подзадачами.
Но в общем, все решаемо, думаю завтра доделаю и выложу на тест. :)
Поддержки 2003 Excel не будет, т.к. он не имеет всех функций, которые для этого анализа необходимы.
Надеюсь, все, кому интересен Excel, уже установили себе версию посвежее.