Постановка проблемы, моделирование данных и кластерный анализ

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

В науке о данных кластеризация - это процесс группировки объектов по некоторым общим признакам.

Видите связь? Кластеризация - метод науки о данных - хорошо подходит для сегментации клиентов - варианта использования. Тем не менее, как это часто бывает, когда мы начинаем копать, это еще не все. Мы называем это моделированием.

Давайте начнем с рассмотрения конкретных черт, по которым мы хотим сегментировать. Мы будем проводить различие между маркетингом B2B и маркетингом B2C, поскольку их черты различаются.

B2B-маркетинг

Заказчиками являются предприятия, то есть компании. Один из наборов признаков, по которым можно провести сегментацию, - это так называемые фирменные данные: отрасль, местоположение, размер компании (малая, средняя, ​​большая и т. Д.).

B2C маркетинг

Здесь покупатели - это потребители, то есть люди. При сегментации полезно учитывать так называемые демографические характеристики: возраст, пол, местоположение, этническую принадлежность, уровень дохода и т. Д.

Моделирование

Теперь мы абстрагируемся от специфики B2B и B2C и посмотрим на моделирование как таковое. В качестве иллюстрации мы будем использовать примеры B2B, но моделирование носит более общий характер.

Единый структурированный фактор

Сначала рассмотрим одну особенность, скажем, промышленность. Мы хотим сегментировать клиентов именно по этому признаку. Во-первых, предположим, что промышленность имеет небольшое количество чистых ценностей. («Чистый» означает из контролируемого словаря - например, из раскрывающегося списка.)

Эту сегментацию легко сделать. Он просто включает в себя группировку и агрегирование.

Единый неструктурированный фактор

Теперь предположим, что значения отрасли не чисты. Они хранятся в текстовом поле в произвольной форме. При вводе данных ставится любое значение, имеющее смысл.

Допустим, в нашей базе данных 100 000 записей о клиентах, и в большинстве из них заполнены значения полей industry.

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

Мера схожести строк: Первая разумная попытка решить эту проблему выглядит примерно так. Сначала мы определяем меру сходства для пар отраслевых строк. Начнем с определения набора слов в строке отрасли. Это просто набор различных токенов в строке. Люди, знакомые с термином мешок слов, могут подумать об этом как о мешке с удаленной частотой слов. Затем, имея два набора слов, нам нужен разумный способ количественно оценить их сходство. Вот один из них: это называется сходство по Жаккару.

Сходство Жаккара двух наборов - это количество общих элементов, деленное на количество элементов в их объединении.

Ниже приведен пример.

Jaccard-coefficient({predictive analytics platform},{predictive analytics}) = ⅔

Группирование записей в кластеры. Затем нам нужно сгруппировать записи в кластеры, используя эту меру сходства. Пары записей в одном кластере должны быть похожи друг на друга; пар в разных кластерах нет.

Легче сказать, чем сделать. Непонятно, полностью ли мы продумали нашу постановку задачи. Я уточню. Слово «группа», кажется, подразумевает, что запись должна входить ровно в один кластер. Неужели это то, чего мы хотим? Не обязательно. Представьте себе отраслевую ценность Медицинская информатика. Мы могли бы разделить это на несколько кластеров - некоторые из них связаны с медициной, некоторые с ИТ.

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

Алгоритмы кластеризации. Какой алгоритм использовать, зависит от того, какой тип кластеризации мы хотим - плоскую или иерархическую? Даже внутри плоской категории алгоритм зависит от того, хотим ли мы, чтобы кластеризация была жесткой или мягкой. (Hard означает, что элемент принадлежит ровно одному кластеру.)

Плоская кластеризация. Алгоритмы, подходящие для жесткой кластеризации, включают k -средства кластеризации, сканирование баз данных, кластеризацию подключенных компонентов и другие. Алгоритмы мягкой кластеризации часто являются смягченными версиями алгоритмов жесткой кластеризации. Одним из таких способов является мягкая, также называемая вероятностной, кластеризация k. Это основано на мощном вызове алгоритма EM, частным случаем которого является (жесткая) кластеризация k-средних.

Иерархическая кластеризация. Популярные алгоритмы иерархической кластеризации включают агломеративную (восходящую) кластеризацию или разделяющую (нисходящую) кластеризацию. В первом случае элементы сначала группируются в плотные кластеры, а затем кластеры объединяются в более крупные кластеры. Этот процесс повторяется до тех пор, пока у нас не появится дерево кластеров. Его листья являются предметами. Корень дерева - это отдельный кластер, представляющий весь набор данных.

Разделительная кластеризация работает в обратном направлении. Он начинается с кластера, представляющего весь набор данных; затем кластер делится на две части. Полученные кластеры становятся потомками первого. Таким образом дерево кластеров растет сверху вниз.

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

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

Лингвистическая структура в отраслевых названиях. Возвращаясь к нашей отрасли на примере неструктурированных ценностей, мы могли бы избрать третий курс. Воспользуйтесь преимуществами лингвистической структуры, неявно присутствующей в отраслевых названиях. Это, вероятно, сработает лучше. Мы проиллюстрируем это ниже на игрушечном примере. Появляющийся алгоритм можно легко улучшить, чтобы он соответствовал более реалистичным сценариям.

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

Software ← Database Software, Software ← Analytics Software
Manufacturing ← Auto Manufacturing, Manufacturing ← Drug Manufacturing

где p ← c обозначает родительско-дочерний экземпляр.

Алгоритм, использующий лингвистическую структуру. Ниже представлен алгоритм. В этом примере это даст желаемую иерархию.

Order the set of distinct industry values by the number of words in them. Least number of words first. Denote this ordering as I1, I2, …, Ik.
For each i in 1..k
   If Ii does not have a parent, set Ii as a root of the hierarchy.
   For each j in (i+1)..k
      If Ij’s parent is not set and is_child(Ij,Ii)
          parent(Ij) = Ii

Проиллюстрируем этот алгоритм на нашем примере. Сначала мы сортируем отраслевые названия по количеству слов в них. Это дает упорядоченный список

Software, Manufacturing, Database Software, Analytics Software, Auto Manufacturing, Drug Manufacturing

Затем мы делаем Software корневым и сканируем вправо от него, чтобы найти всех его дочерних элементов. Мы открываем

Software ← Database Software, Software ← Analytics Software

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

Manufacturing ← Auto Manufacturing, Manufacturing ← Drug Manufacturing

Затем мы пытаемся найти потомков каждого из двух слов отраслевых названий. Мы ничего не находим. Итак, мы закончили.

Множественность факторов, смешанная структура

Теперь рассмотрим сегментирование компаний по совокупности нескольких факторов. В частности, по ключевым характеристикам фирмы: отрасли, местоположению и размеру компании. Некоторые из этих факторов могут быть структурированными, другие - неструктурированными. Например, промышленность по-прежнему неструктурирована. Размер компании может быть структурирован: представлен фиксированным количеством значений, например small, medium, large. Это значительно усложняет задачу.

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

Преамбула 1. Описание факторов. Во-первых, давайте уточним наши описания факторов. Мы по-прежнему сохраним неструктурированность отрасли. Мы сделаем размер компании порядковым номером. Это просто означает, что размер компании будет иметь фиксированный набор упорядоченных значений. Например, small, medium, large. Позже мы сможем добавить дополнительные значения к размеру компании, например очень маленький и очень большой. Мы даже можем настроить набор значений автоматически с помощью процесса биннинга размера компании на основе данных. Результирующие значения могут отличаться от набора данных к набору данных. Пока значения можно заказать, мы в порядке. (Между прочим, не каждый набор значений можно упорядочить. Считайте, что пол = женский, мужской. Естественного порядка не существует. Мы могли бы наложить какой-то искусственный порядок, но это может пойти не так хорошо.)

Что касается местоположения, давайте начнем с простоты и просто выберем 5-значный почтовый индекс. (Это ограничивает нахождение наших компаний только в США.)

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

Показатели сходства для отдельных факторов

Мы воспользуемся подходом к определению показателей сходства для каждого фактора индивидуально и на их основе построим нашу многофакторную метрику сходства.

Общая часть - сигмовидная функция. Прежде чем мы углубимся в отдельные показатели, мы хотели бы упомянуть ключевой момент, который пронизывает их дизайн. Во всех из них мы используем сигмовидную функцию как мягкое приближение к ступенчатой ​​функции. Мы делаем это, потому что хотим, чтобы сходство быстро снижалось до 0, когда сравниваемые значения недостаточно похожи. Это дает нам контроль над обнаружением сходства по сравнению с показателями ложноположительных результатов.

Поэтому давайте сначала определим сигмовидную функцию.

sigmoid_{a,b}(x) = 1/(1+exp(-a*(x-b)))

a управляет крутизной сигмоиды, то есть степенью, в которой она приближается к ступенчатой ​​функции. b управляет мягким порогом. Так же, как и ступенчатая функция, сигмоид различает значения, фланкирующие b.

Показатель схожести названий компаний. Начнем с показателя для сравнения компаний двух размеров. Давайте расположим значения размера компании в следующем порядке: 1, 2, 3,…, k. Таким образом, 1 обозначает корзину наименьшего размера компании, а k - наибольшую корзину размера компании. Наша метрика подобия

S(i,j) = sigmoid_{a,b}(-|i-j|)

Здесь a>0 и b>0 дают нам контроль над крутизной сигмовидной кишки и порогом. Мы использовали -|i-j| вместо |i-j| в качестве аргумента, потому что мы ищем инвертированное сигмовидное поведение. Вместо этого мы могли бы включить этот отрицательный знак в a, но сделать его явным более интуитивно понятно.

S (i, j) интуитивно догадывается, что чем ближе ячейки i и j в порядке их ранжирования, т. Е. В размерах компаний, которые они представляют, тем выше значение сходства.

Мы выберем разумные настройки по умолчанию, чтобы вы могли забыть о них, если вам не нравятся бесплатные параметры. В частности, мы установим a на 1, наиболее часто используемую крутизну сигмовидной формы. Чтобы лучше понять, какое значение b имеет смысл, давайте перепишем сигмоид как sigmoid(b-|i-j|). Мы установим b на 1.5. Это приведет к тому, что когда |i-j|<=1.5 значение сигмоида будет пересекать 0,5 снизу. Конечно, мы можем настроить это поведение по своему желанию.

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

S(z1,z2) =sigmoid_{a,b}(-|z1-z2|)

На этот раз мы выберем a>0, чтобы он был намного меньше 1 и b до ~ 20. Интуиция подсказывает, что мы хотим, чтобы S (z1, z2) было больше 0,5, даже если | z1-z2 | примерно 20 лет. Плюс хотим, чтобы у переезда была небольшая крутизна. Мы, конечно, можем настроить эти значения по своему усмотрению.

Ошибки подстановки и перестановки. Хотя этот показатель достаточно хорошо моделирует близость, он не учитывает ошибки подстановки или перестановки. Давайте начнем с рассмотрения каждого из них. (Мы намеренно опустили ошибки вставки и удаления, поскольку они изменяют количество цифр.)

Substitution error: 21034, 21834, Transposition error: 21034, 20134

Как и в приведенных выше примерах, мы будем рассматривать только ошибки замены одиночных цифр и ошибки транспонирования смежных цифр. Вот простая метрика, учитывающая ошибки подстановки одной цифры:

S2(z1,z2) = sigmoid_{a,b}(-sum_i NE(z1[i],z2[i]))

Здесь NE(x,y) равно 0, когда x равно y, и 1, когда нет. Мы установим a на 1 и b на 1,5, поскольку поведение, которое мы ищем (на основе аргумента сигмоида), является именно тем, что мы искали для схожести размеров компании.

Точно так же мы можем определить метрику, которая вмещает до одной транспозиции соседних цифр.

T(z1,z2) = sigmoid_{a,b}(-#adjacent-digit-transpositions(z1,z2))

Мы используем те же a и b, что и для подсчета очков за замену.

Итак, теперь мы можем объединить все эти метрики в одну метрику.

Sim(z1,z2) = Max(S(z1,z2),S2(z1,z2),T(z1,z2) )

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

S_industry(I1,I2) = sigmoid_{a,b}(Jaccard-coefficient(I1,I2))

Мы не будем подробно описывать, как выбрать значения по умолчанию a и b. Скорее, мы просто отметим, что a должно быть положительным и больше 1 и b должно быть выбрано как значение коэффициента Жаккара, которое, как мы считаем, находится на грани сходства. Обратите внимание, что коэффициент Жаккара возвращает значение от 0 до 1, где 0 означает максимально разное, а 1 означает максимальное сходство.

Многофакторный показатель

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

Наша многофакторная метрика

S(C1,C2) = w_zip*S_zip(C1.zip,C2.zip) + w_industry*S_industry(C1.industry,C2.industry) + w_company_size*S(C1.company_size_bin_rank,C2.company_size_bin_rank)

Факторные веса позволяют нам контролировать относительное влияние индивидуальных сходств факторов на общую метрику.

Специализации: теперь, когда у нас есть эта метрика, мы можем построить ее различные специализации, просто установив определенные весовые коэффициенты на 0. Таким образом, мы можем реализовать все однофакторные версии - схожесть по индексу, схожесть- по отраслям, схожесть по размеру компании, а также все двухфакторные версии. Вооружившись этими специализациями, мы можем более гибко строить сегменты. Фактически мы можем группировать по одному, двум или всем трем факторам. Обратите внимание, что «группировать по» на самом деле означает «нечеткую группу по».

Кластеризация матрицы сходства. Ключевой момент, который мы хотели бы подчеркнуть, заключается в том, что естественный способ использования определенных нами показателей попарного сходства - это вычисление попарного сходства между всеми парами компаний и их фиксация. в матрице подобия. (За исключением случаев, когда количество компаний настолько велико, что вычисление попарного сходства будет выполняться слишком медленно. Мы предполагаем, что это не так.)

Затем алгоритмы кластеризации могут работать непосредственно с этой матрицей. Это разделяет опасения. Алгоритмы кластеризации работают только с матрицей подобия, не заботясь о том, как она была создана. Метрики подобия сосредоточены на количественной оценке фактического сходства, не заботясь о том, как объекты будут сгруппированы ниже по потоку.

Конкретный алгоритм - разбиение графа. Давайте посмотрим на конкретный алгоритм кластеризации на основе матрицы сходства. Мы представим матрицу в виде графика. Узлами графа являются объекты, в нашем случае компании. Два узла соединяются ребром, если соответствующие объекты достаточно похожи. Вес на грани фиксирует фактическое значение сходства.

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

Давайте уточним это описание. Сначала нам нужны некоторые ключевые концепции.

Плотность подграфа: мы определяем плотность подграфа на k узлах как сумму весов на ребрах, которые соединяют пары узлов в этом наборе, деленную на k (k -1) / 2. Это предполагает, что вес на ребре находится между 0 и 1. Не ребра могут рассматриваться как ребра с весом 0. В этом представлении плотность подграфа - это средний вес ребра в нем.

Веса узла: мы определяем вес узла как сумму весов ребер, соприкасающихся с узлом. Мы определяем вес узла в наборе узлов как сумму весов ребер, соприкасающихся с этим узлом, чья другая конечная точка находится в этом наборе. Например, вес узла a на узлах b, c и d представляет собой сумму веса краев a - b, a - c и a - d.

Фактический алгоритм. Далее мы опишем простой эвристический алгоритм, который находит хорошую кластеризацию.

find_one_good_cluster(G)
   C = {v}, where v is a highest-weight node in G
   Repeat
     Find a node v in G-C whose weight on C is
     sufficiently high.
     If no such v exists 
       Close C.
       remaining_clusters = find_one_good_cluster(G-C)
       Return remaining_clusters + {C}
     Else
       Add v to C
   forever

«Достаточно высокий» тест смещает алгоритм поиска плотных кластеров. (Плотность не гарантируется, поскольку проверка плотности выполняется только тогда, когда узел добавляется в кластер.) Алгоритм явно не поддерживает разреженность между кластерами. Это происходит неявно. Кластер продолжает расти, пока узел за его пределами имеет достаточно высокий совокупный вес для узлов в нем. Следовательно, когда кластер перестает расти, все узлы за его пределами имеют низкий совокупный вес для узлов в нем. Это способствует разреженным межкластерным регионам.

Резюме

В этом посте мы увидели, как кластеризация как метод анализа данных хорошо подходит для сегментации рынка в качестве варианта использования. Мы изучили факторы, которые следует использовать для сегментации B2B и B2C. Мы изучили проблемы, которые возникают, когда коэффициент имеет чистые значения; когда фактор имеет длинный хвост неструктурированных значений; и когда фактор имеет небольшой набор порядковых значений.

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

Мы представили конкретные показатели для количественной оценки сходства некоторых типов факторов, с которыми мы сталкиваемся в настройках B2B. Затем мы представили многофакторную меру сходства и описали, как использовать ее в многофакторной кластеризации (подумайте о сегментировании рынка по комбинации нескольких факторов).