В предыдущих статьях я рассмотрел Априорный алгоритм и хэш-функции в контексте интеллектуального анализа данных. Если вы не знакомы с этими концепциями, я рекомендую уделить время их прочтению.
Алгоритм Apriori находит частые наборы элементов, выполняя несколько проходов по набору данных. При первом проходе подсчитываются отдельные элементы (иногда называемые синглетонами), а те, которые имеют достаточно большое количество (или поддержки), считаются частыми синглетонами. При втором проходе по данным учитываются только пары кандидатов. Эти пары состоят из двух частых одиночек.
Скорее всего, количество пар кандидатов значительно меньше количества возможных пар в наборе данных. Даже в этом случае количество пар кандидатов может быть довольно большим. Это делает второй проход алгоритма априори очень требовательным к памяти. Фактически, это часто самый требовательный к памяти проход алгоритма [1]. В этих случаях уменьшение требований к памяти на втором проходе уменьшило бы общие требования к памяти для алгоритма.
Количество пар кандидатов тесно связано с количеством пар, которые могут быть созданы с использованием всех часто используемых элементов. Это потому, что любая пара, состоящая из двух часто встречающихся элементов, считается парой-кандидатом. Тем не менее, имейте в виду, что не все эти пары будут встречаться в наборе данных. Например, даже если {яблоко} и {банан} являются часто используемыми элементами, возможно, что пара {яблоко, банан} не появится в наборе данных. Давайте назовем эти пары возможными парами кандидатов и зарезервируем термин пары кандидатов для пар, которые мы фактически считаем.
В результате, если у нас есть N частых элементов, биномиальный коэффициент N select 2 дает нам количество возможных пар кандидатов. На графике ниже показано количество возможных пар кандидатов в зависимости от количества часто используемых элементов. Мы видим, что требования к памяти будут расти довольно быстро по мере увеличения количества часто используемых элементов, поскольку количество возможных пар кандидатов стремительно растет.
Опять же, имейте в виду, что некоторые из этих пар могут не обязательно отображаться в нашем наборе данных, но количество пар, которые мы будем подсчитывать (т.е. пары кандидатов), прямо пропорционально количеству возможных пар кандидатов. .
Вот похожий график, но с логарифмической шкалой по оси Y:
В связи с этим подсчет количества часто используемых элементов не занимает много памяти, а это означает, что во время первого прохода алгоритма априори будет много неиспользуемой памяти. Может быть, ему удастся найти хорошее применение ...
Именно это и сделали Пак, Чен и Ю в своем алгоритме на основе хэша для правил ассоциации майнинга, который в честь авторов был сокращенно назван PCY [1]. Алгоритм использует хеширование во время первого прохода, чтобы уменьшить количество пар кандидатов, рассматриваемых во втором проходе.
Ключевая интуиция
Представьте, что вместо подсчета количества каждого элемента в наборе данных мы подсчитали количество элементов, которые начинались с каждой буквы алфавита.
Если бы количество элементов, начинающихся с буквы 'a', было меньше нашего порога поддержки, мы бы знали, что ни один из элементов, начинающихся с буквы 'a' часты. Например, если бы часто были яблоки, то количество элементов, начинающихся с ‘a’, было бы выше нашего порогового значения.
Это ключевая идея, лежащая в основе алгоритма PCY. Вместо того, чтобы применять его к отдельным элементам, мы применяем его к парам, поскольку пары создают узкое место в нашей памяти. Но принцип тот же.
(Примечание: на практике мы используем модифицированную хеш-таблицу, а не первые буквы элементов, но, надеюсь, этот пример поможет построить интуитивное понимание алгоритма)
PCY с глупой хеш-функцией
Чтобы понять, как работает алгоритм PCY, мы рассмотрим его с помощью упрощенной (и глупой) хеш-функции. Имейте в виду, что алгоритм PCY - это немного измененная версия алгоритма априори.
Когда мы сталкиваемся с каждой корзиной во время первого прохода, мы отслеживаем появление каждого сингла. Мы также строим пары из элементов в корзине, хэшируем пары и отслеживаем, сколько раз появлялось каждое хеш-значение.
Механизм, который мы будем использовать для отслеживания этих подсчетов, - это модифицированная хеш-таблица. Каждый сегмент в хеш-таблице соответствует одному из хешей и содержит одно целое число, которое представляет количество раз, когда что-то хешировалось в этом сегменте.
Обратите внимание, что это сильно отличается от отслеживания всех пар, хэшированных в этом сегменте.
В этом примере мы будем хэшировать эти пары, используя упрощенную хеш-функцию.
Определение нашей хеш-функции
Для каждой пары мы записываем первую букву в названии каждого элемента и складываем их в отсортированную строку. Затем мы ведем хеш-таблицу с подсчетом всех вхождений этих отсортированных строк.
Чтобы проиллюстрировать это, рассмотрим корзины ниже.
Пусть s = 3 будет отсечкой поддержки, чтобы считаться «частым».
Наш набор данных:
яблоки, авокадо, бекон, черника, морковь
миндаль, авокадо, бекон, бананы, дуриан
миндаль, бекон
авокадо, бананы
миндаль
Мы читаем информацию в первой корзине и обновляем счетчик товаров. Это первая корзина, которую мы видим, поэтому каждый товар будет иметь счет 1 после обработки этой корзины.
Затем мы генерируем все возможные пары из предметов в этой корзине:
В корзине:
яблоки, авокадо, бекон, черника, морковь.
Возможные пары:
{яблоки, авокадо}
{яблоки, бекон}
{яблоки, черника}
{яблоки, морковь}
{авокадо, бекон}
{авокадо, черника}
и так далее…
Для каждой из этих пар мы берем первую букву в каждом элементе и складываем их в строку, которую мы сортируем в алфавитном порядке. Это наша хеш-функция, что немного глупо, но, надеюсь, поможет развить интуицию.
Вот несколько пар и соответствующие им хеши:
{яблоки, авокадо} → 'aa'
{яблоки, бекон} → 'ab'
{яблоки, черника} → 'ab'
…
{авокадо, бекон} → 'ab'
и так далее…
Затем мы отслеживаем, сколько раз появлялся каждый хеш. Например, после первой корзины хэш ‘aa’ будет иметь счетчик 1, а хэш ‘ab’ будет иметь счетчик 4.
Например, пара {яблок, бекон} хешируется до 'ab', поэтому, когда мы встретим это, мы перейдем к ведру в хеш-таблице, соответствующей 'ab', и увеличьте количество там с 0 до 1. Пара {яблок, черника} также хешей в 'ab', поэтому мы увеличим счетчик в этом сегменте с 1 до 2.
Обратите внимание, что каждая из этих пар до сих пор появлялась только один раз, но счетчик в этой корзине равен 2, поскольку обе пары хешируют одну и ту же корзину.
Обратите внимание, что каждая из этих пар до сих пор появлялась только один раз, но счетчик в этой корзине равен 2, поскольку обе пары хешируют одну и ту же корзину.
Мы повторяем это для всех корзин в наборе данных, и в конце всего первого прохода по набору данных мы получаем результаты, показанные ниже. (Помните, что наш порог поддержки частого использования набора элементов равен s = 3).
Часто встречающиеся:
миндаль, авокадо, бекон.
Количество парных хэшей:
'aa': 2
'ab': 10
'ac': 2
'ad': 2
'bc': 2
'bd': 2
Что мы можем сделать с этими подсчетами хешей?
Вы могли заметить, что у хеша ‘ab’ счетчик превышает наш порог поддержки. Однако, если мы смотрим только на эти подсчеты ведер, нам трудно определить, как мы дошли до этого количества.
С одной стороны, могло случиться так, что одна пара с хешем ‘ab’ появлялась в наборе данных 10 раз. С другой стороны, может случиться так, что в эту корзину хешируется много разных пар. Таким образом, в корзине может быть высокий счетчик, даже если ни одна из пар, хеширующих эту корзину, не является частой.
В отличие от этого очень важны сегменты с количеством меньше, чем наш порог поддержки. Рассмотрим, например, сегмент 'ad', счетчик которого равен 2. Мы не знаем, появлялась ли пара, хеширующая тег 'ad', дважды в набор данных или две разные пары, каждая из которых хеширует эту корзину, появлялась один раз. Но если бы какая-либо из пар, которые хешировали для этого ведра, были частыми, в ведре было бы счетчик 3 или более. Это означает, что любая пара, хеширующая сегмент ‘ad’, должна быть нечастой парой, поскольку счетчик этого сегмента ниже нашего порогового значения поддержки, равного 3.
... любая пара, хеширующая сегмент ad, должна быть нечастой парой, поскольку количество в этом сегменте ниже нашего порогового значения поддержки, равного 3.
Например, если пара {яблоко, дуриан} появлялась в наборе данных 5 раз, то в сегменте 'ad' будет подсчитано не менее 5, поскольку эта пара хеширует сегмент 'ad'. Другими словами, количество сегментов представляет собой максимально возможное количество раз, когда любая пара, хеширующая этот сегмент, может появиться в наборе данных.
Это позволяет нам сузить определение пары кандидатов во время второго прохода по набору данных, что значительно снижает количество возможных пар кандидатов. В частности, мы потребуем, чтобы пара хешировалась в частую корзину, чтобы быть парой-кандидатом, помимо того, что она состояла из часто встречающихся элементов.
Что происходит с хеш-таблицей после первого прохода?
Во время второго прохода нам нужно только знать, является ли сегмент в хеш-таблице частым - нас не волнует конкретный счетчик. Поскольку часто против нечасто является двоичным, мы можем заменить счетчик в хеш-таблице на единицу 1 или 0. Таким образом мы уменьшим объем памяти, занимаемый каждым сегментом в хеш-таблице с 4-байтовый int, в котором хранится счетчик, до 1-битного флага, который сообщает нам, часто ли это ведро. Результирующая хеш-таблица часто называется растровым изображением.
Держать на секунду…
Если вы внимательно следите, то, возможно, заметили, что в представленном здесь небольшом наборе данных отслеживание этих хеш-счетчиков на самом деле нам никак не помогает. Пары, которые мы бы отфильтровали с помощью нечастых сегментов, уже отфильтрованы из-за того, что элементы, которые они содержат, встречаются нечасто. Это потому, что наш набор данных искусственно мал.
При больших наборах данных и большом количестве товаров, продаваемых в магазине, это крайне маловероятно. На практике решающим фактором в отношении того, обеспечивает ли PCY улучшение по сравнению с Apriori, является процент возможных пар кандидатов, которые исключаются методом хеширования. Мы рассмотрим это чуть позже.
Краткое примечание о нашей хеш-функции
Здесь следует иметь в виду одну важную вещь: выбранная нами хеш-функция очень надумана. Самый большой недостаток этой хеш-функции заключается в том, что хеш-коды не имеют равной вероятности появления. (Чтобы освежить в памяти хеш-функции, прочтите Хеш-функции для интеллектуального анализа данных, где описаны некоторые примеры хэш-функций, которые мы могли бы использовать в продакшене, ближе к концу поста.)
Компромиссы с размером хеш-таблицы
Основной компромисс, с которым приходится сталкиваться при выборе размера хэш-таблицы, заключается между объемом памяти, занимаемой хэш-таблицей, и количеством возможных конфликтов.
Рассмотрим, например, случай, когда количество сегментов в хеш-таблице равно количеству возможных пар кандидатов. В этом случае объем памяти, занимаемый хэш-таблицей, чрезвычайно велик, и мы могли бы просто посчитать все пары кандидатов.
С другой стороны, если мы сделаем нашу хеш-таблицу очень маленькой - например, одной корзиной - мы столкнемся с огромным количеством коллизий, что также не особенно полезно.
В исходной статье размеры хеш-таблиц рассматриваются более подробно, и я рекомендую вам прочитать ее, если вам интересно [1]. Онлайн-класс Mining Massive Datasets, у которого есть соответствующий учебник, который находится в свободном доступе через их веб-сайт, также подробно обсуждает алгоритм PCY. В книге утверждается, что точка безубыточности для использования техники, описанной в алгоритме PCY, - это когда 2/3 возможных пар кандидатов удаляются в процессе хеширования. Я исследую математику этого утверждения в другом посте: Использование памяти PCY против априорных алгоритмов.
Друзья алгоритма PCY: многоэтапность и мультихеш
Как следует из названия этого поста, есть несколько усовершенствований, которые можно сделать для улучшения алгоритма PCY - два, которые мы рассмотрим здесь, - это многоэтапный алгоритм и алгоритм мультихеширования.
Оба алгоритма сосредоточены на применении фильтрации на основе хешей из алгоритма PCY более одного раза, чтобы еще больше уменьшить количество возможных пар кандидатов.
Многоступенчатый алгоритм
В многоэтапном алгоритме мы начинаем с проведения первого прохода по данным, как мы это делали в алгоритме PCY. Однако перед тем, как перейти к подсчету пар кандидатов, мы проводим вторую передачу пар данных и хешей во вторую хеш-таблицу тогда и только тогда, когда выполняются следующие условия:
- Пара состоит из часто встречающихся предметов
- Пара хеширует частую корзину в нашем первом растровом изображении.
Но будьте осторожны: если мы воспользуемся той же хеш-функцией, которую использовали для создания первой хеш-таблицы, мы не получим никакой новой информации. Вторая хеш-таблица должна использовать хеш-функцию, независимую от первой хеш-таблицы. Если мы не введем новую хеш-функцию, мы получим ту же хеш-таблицу, что и раньше, за исключением того, что нечастые сегменты будут удалены.
Если мы не введем новую хеш-функцию, мы получим ту же хеш-таблицу, что и раньше, за исключением того, что нечастые сегменты будут удалены.
После завершения второго прохода данных мы создаем растровое изображение из второй хеш-таблицы. Вместе два созданных нами растровых изображения будут отфильтровывать большее количество пар, чем одно только первое растровое изображение.
Во время третьего прохода мы подсчитываем пары, состоящие из часто встречающихся элементов, и хешируем частые сегменты в обоих растровых изображениях. Добавленное растровое изображение эффективно снижает количество ложных срабатываний.
Перед подсчетом пар кандидатов мы могли бы выбрать любое количество проходов по выбранным нами данным. Целью здесь было бы отфильтровать более редкие пары и уменьшить объем памяти, занимаемый алгоритмом.
Однако имейте в виду, что хэш-таблицы и растровые изображения также занимают память, и наступит момент, когда больше не имеет смысла продолжать передавать данные. Кроме того, мы должны учитывать, что каждый проход данных требует времени.
… Имейте в виду, что хэш-таблицы и растровые изображения также занимают память, и наступит момент, когда больше не имеет смысла продолжать выполнять проходы над данными.
Можем ли мы хешировать вещи исключительно через второе (или n-е) растровое изображение?
Нет, не можем. Причина в том, что второе растровое изображение было построено только из подмножества всех возможных пар. Рассмотрим, например, пару, которая состоит из часто используемых элементов, но не хеширует частый сегмент в первом растровом изображении. Поскольку он не выполняет хеширование для частой корзины в первом растровом изображении, мы знаем, что это не частая пара. Но подумайте, что может случиться, если мы пропустим эту пару через второе растровое изображение. Второе растровое изображение - совершенно неизведанная территория для него, поскольку не играло никакой роли в построении этого растрового изображения. Мы могли бы пройти через это и обнаружить, что - просто случайно - он хеширует частую корзину. Если мы только хэшируем эту пару через второе растровое изображение, мы можем случайно подумать, что это пара-кандидат. Использование обоих растровых изображений гарантирует, что мы отфильтруем их.
Если мы будем отслеживать порядок, в котором были созданы растровые изображения, мы можем сэкономить немного времени, хешируя пары через 1-е растровое изображение, прежде чем решить, следует ли хешировать его через второе растровое изображение. Таким образом, если оно будет отфильтровано как нечастое, мы не будем тратить время на последующие растровые изображения.
Помните: растровые изображения предоставляют информацию только о парах, которые использовались для их построения.
Алгоритм Multihash
Подобно многоступенчатому алгоритму, многоступенчатый алгоритм также использует несколько хеш-таблиц для фильтрации нечастых пар. Однако вместо того, чтобы выполнять дополнительные проходы по данным, этот алгоритм просто создает более одной хеш-таблицы во время первого прохода. Эти хеш-таблицы превращаются в растровые изображения, которые используются для фильтрации нечастых пар во время второго прохода.
Количество используемых хеш-таблиц можно настраивать в зависимости от контекста. Использование большего количества хэш-таблиц - до определенного момента - будет означать, что мы отфильтруем более редкие пары.
Добавление хэш-таблиц требует выбора - мы можем либо увеличить объем памяти, который мы используем, либо мы можем решить не увеличивать использование памяти и просто разделить память между хеш-таблицами.
Имейте в виду, что разделение памяти между многими хеш-таблицами означает, что хеш-таблицы становятся меньше, что приводит к большему количеству конфликтов. Если у нас слишком много коллизий, мы не сможем эффективно отфильтровать редкие пары.
При поиске компромиссов рассмотрение крайних случаев обычно помогает развить интуицию. Например, рассмотрим случай, когда у нас много-много хеш-таблиц, каждая из которых имеет только одну корзину. Каждая хеш-таблица будет содержать общее количество всех пар в наборе данных, что не дает никакой помощи.
При поиске компромиссов рассмотрение крайних случаев обычно помогает развить интуицию.
В заключение
В интеллектуальном анализе данных, какие алгоритмы мы используем и как мы настраиваем их параметры, очень зависит от контекста. В этом посте мы увидели, что использование алгоритма PCY сокращает объем нашей памяти только в определенных ситуациях. Мы также видели, что количество проходов / хэш-таблиц, используемых в многопроходных и многоступенчатых алгоритмах, сильно зависит от контекста.
Реализуйте, внедрите, внедрите!
Эти решения, основанные на контексте, требуют практики. Чтобы лучше понять их, я настоятельно рекомендую вам попробовать реализовать эти алгоритмы самостоятельно.
Если вы ищете наборы данных для практики, я рекомендую:
- Это репозиторий Github, который я создал с примерами наборов данных
- Конкурс Instacart Market-Basket Analysis на Kaggle
Дайте мне знать, что вы думаете об этом сообщении, в комментариях ниже.
И не забудьте подписаться на Data Science Weekly, чтобы видеть больше подобного контента.
использованная литература
[2]: Mining Massive Datasets - онлайн-урок с бесплатным учебником.
