Модификация алгоритма FP Growth или как правильно ухаживать за своими деревьями

Привет, Хабр!

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

О себе

Немного о себе и о задаче, которую мне предстояло решить: меня зовут Савелий Батурин, я — начинающий Data Science инженер в компании, занимающейся разработкой и поддержкой мобильных приложений. Несмотря на статус «начинающего», мне была удостоена честь возглавить только-только зарождающийся отдел и сходу перейти к решению нетривиальных задач, например, таких как разработка рекомендательных систем для уже долгое время существующих и собирающих обширную базу данных компаний, развивающихся в направлении фудтеха. Я имею большой опыт в разработке приложений для мобильных устройств, решении задачек по олимпиадному программированию, да и в целом — образование прикладного математика. Однако, непосредственно опыта в области рекомендательных систем было ещё маловато, поэтому решил не лезть в коллаборативные и нейро-рекомедеры, а начать с чего-то попроще — поиска ассоциативных правил.

Введение

Начнем с того, что вообще стоит почитать/посмотреть для комфортного восприятия данной статьи:

• Ассоциативные правила, или пиво с подгузниками — легкая замечательная статья, дающая краткий экскурс в мир ассоциативных правил

• Машинное обучение. Поиск ассоциативных правил. К.В. Воронцов, Школа анализа данных, Яндекс. — уже не такое легкое, но не менее замечательное видео для более глубокого понимаю того, как именно работает FP Growth алгоритм

Теперь, полагая, что вы знакомы с тем, как строить FP-деревья и извлекать из них частые наборы — рассмотрим, что вообще здесь не так, а точнее — что не так с непосредственным приложением наивной реализации FP Growth к реальной задаче. Существует множество решений из коробки, которые дают возможность строить FP деревья и доставать из них частые наборы, однако ни в одном из рассмотренных мною готовом решении не было поддержки так называемого «дообучения». Лично мне показалось, что такого понятия вообще не существует в контексте построения FP дерева, но ничего — никто не запрещает нам его ввести самостоятельно.

Пусть у нас есть изначальный транзакционный датасет A, на котором уже построено FP-дерево T(A) и отсортированный по убыванию поддержки список признаков H(A). Текущий датасет с вновь полученными данными обозначим, как C. Главный вопрос — как имея на руках изначальное дерево T(A) и отсортированный список признаков H(A), построить «дополненное» дерево T(C) так, чтобы не пришлось заново строить с нуля всё дерево T(C). Пусть также B — новые неучтённые данные, причём B=C \ A. Проблема особенно актуальна, если A — огромная, годами накопленная база данных, а B — накопившаяся за последнюю неделю статистика, которую тоже хотелось бы учесть. Дообучением назовём процесс получения дерева T(C) из T(A), используя B и H(A). Символически дообучение обозначим следующим образом:

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

«Ладно», — подумал я сперва — «чего тут сложно? Возьмем датасет B, обновим соответствующим образом список H(A), отсортируем его по убыванию поддержки и продолжим пополнять дерево, будто процесс обучения и не прерывался».

Стоит отметить, что в упомянутом ранее ШАДовском видео от Яндекс лектор на 45:13 вскользь сказал, что при получении новых данных мы просто обновляем отсортированный список признаков H(A) := H(C) и продолжаем строить дерево дальше в соответствии с этим списком. Причём даже не обязательно это делать с нуля, достаточно добавить статистику H(B) к H(A) и отсортировать полученный список за nlog(n). Как же всё просто звучит! Первоначально я так и сделал, но меня начало преследовать жгучее ощущение того, что в моей жизни что-то пошло не так. Моё FP дерево стало неухоженным — у него появилось много слабых веток, ресурсы на формирование которых могли бы пойти на укрепление уже существующих. Следующая схема прояснит, что я имею ввиду.

Простейший пример

Возьмем для примера простейшую транзакционную базу данных из 6 элементов. Всего будет иметься два айтема a и b, причём изначально a популярнее b:

Допустим у нас появились новые данные B. Тогда обновленный отсортированный список H(C) будет получен следующим образом:

Заметьте, я пишу H(C), поскольку в результате подобного сложения мы и получили H(A∪B)≡H(C). Однако, будет ли дополненное дальше дерево деревом T(C)? Давайте посмотрим. При этом символически обозначим операцию дополнения дерева знаком ‘+’:

Слева у нас дерево, которое дополнено данными из B по способу из лекции, а справа — дерево, которое построено изначально на всем итоговом датасете C=A∪B. Слева появился новый узел b:2 из-за того, что в корне дерева T(A) нет айтемов с таким названием. Что нам дал этот частный пример? А то, что T(A)+B≠T(C) в общем случае! Следовательно, мы не можем просто каждый раз сортировать список айтемов по их поддержке и продолжать строить дерево. Конечно, на больших объемах данных мы будем получать что-то похожее на T(C), но далеко не то же самое.

Отлично, мы поняли, что нельзя просто так брать и продолжать строить дерево на полученных данных, ориентируясь на отсортированный список айтемов. Что же тогда делать? Если внимательно приглядеться к рассмотренному выше примеру, можно увидеть, что в первом случае для того, чтобы получить дерево T(C), нам достаточно было перед процессом обучения поменять узлы a и b местами. То есть b станет родителем для a там, где a был родителем для b. При этом, если a.support-b.support≠0 (разность поддержек не нулевая), то после перестановки перестанет выполняться свойство антимонотонности, которым должно обладать FP дерево. В таком случае создаём новый узел для a c первоначальным родителем (в рассмотренном примере у a родителя не было). Значение поддержки в этом узле устанавливаем как a.support-b.support, а в перемещенном — просто b.support. Полученное в результате такой перестройки дерево и соответствующий список айтемов обозначим, как T'(A) и H'(A). На словах сложно, посмотрим на схеме, что получится в результате такого алгоритма, если взять наш изначальный пример:

Теперь построим дерево T'(A)+B и сравним его с деревом T(C):

Вот теперь T'(A)+B=T(C). Ура! Мы научились перестраивать простые деревья таким образом, что у нас сработало долгожданное дообучение. Но что, если дерево у нас посложнее: имеет ветвления и состоит более чем из 2 айтемов? Давайте опять рассмотрим частный пример, который уже можно будет при желании экстраполировать на деревья любой сложности.

Пример посложнее

Так-то лучше! Теперь составим датасет B так, чтобы айтемы b и d поменялись местами в отсортированном списке. Для наглядности предлагаю сразу рассмотреть результат, а потом уже я объясню непосредственно сам алгоритм:

Обсудим правила, по которому произошла перестройка дерева:

1. Везде, где узел b является родителем узла d происходит следующая замена: узел d становится родителем узла b, а узел d приобретает в качестве родителя первоначального родителя узла b (в данном случае — это узелы a и с). Если у первоначального родителя узла b уже имеется ребёнок с именем d, то свапнутый узел и уже имеющийся узел объединяются, складывая свои поддержки и объединяя детей. Этот свап хорошо виден на схеме

2. Дети узла d становятся детьми узла b

3. У узла d становится единственный ребенок — свапнутый с ним узел b

4. Если b.support-d.support≠0, то создаём новый узел b у первоначального родителя b и устанавливаем ему в качестве поддержки разность поддержек b и d, передавая также всех детей ≠ d (пути abef и abeh должны остаться несмотря на свап узлов b и d)

Договоримся, что далее упорядочивание списка айтемов по их поддержке будет осуществляться при помощи сортировки вставками. Выбор этого алгоритма обусловлен тем, что, во-первых, H(A)+H(B) — в подавляющем большинстве случаев это почти отсортированный массив в силу специфики рассматриваемой задачи, а во-вторых, менять местами при перестройке дерева мы можем только соседние айтемы, что заложено в реализацию выбранной сортировки (свапаем текущий элемент с соседним до тех пор, пока он не займет свое место).

Теперь на каждый свап сортировки неотсортированного списка H(A)+H(B) мы будем выполнять выше изложенные 4 правила. В конечном счёте мы получим отсортированный список H(C) и дерево T'(A) (назовём его также отсортированным). Осталось показать, что T'(A)+B=T(C), для интереса также можете сделать это сами:

Что ж, и тут они совпали — магия! На самом деле это и не мудрено. Я думаю все уже догадались, что при перестройке первоначального дерева, я просто повторяю будущую структуру дерева T(C). Можно перекинуть B в предыдущем равенстве вправо и получить этот вывод символически: T'(A)=T(C)-B.

А если формально?

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

Доказательство проводится в 2 этапа:

1. Единственность доказывается тривиально, поскольку операция построения fp дерева на данном наборе элементов с данным отсортированным списком айтемов устанавливает биективное отображение:

Не так уж много по сравнению с той же теоремой о 4 красках. Мной в этой статье было рассмотрено 2 случая из 8. Оставшиеся 6 выводить не буду, думаю основная идея понятна и если это сильно вас увлечёт, можете попробовать поразмыслить над ними самостоятельно. Теперь остается лишь поставить долгожданные 3 чёрточки знака тождества и вознаградить себя чем-нибудь вкусненьким за проделанную работу: T'(A)+B≡T(C)

Результаты

Это, конечно, всё красиво, а что по результатам? Возьмём объективный показатель — количество узлов в полученных деревьях по старому и новому алгоритмам (где узлов больше, там хуже построено дерево, поскольку данные распыляются по разным веткам, отвечающим за одинаковые айтемсеты):

Для примера возьму транзакционную базу данных одной сети ресторанов в Москве, содержащей 124 тысячи записей. Всего имеется порядка двухсот различных айтемов. При использовании старого алгоритма и обучении на батчах по 1000 элементов с минимальной поддержке, равной 5, получаем дерево, состоящее из 138 тысяч узлов. При использовании модифицированного алгоритма — 124 тысячи узлов. Разница в 14 тысяч узлов достаточно ощутима.

Время работы нового алгоритма незначительно больше старого: в случае без перестройки FP-дерева получаем 1 минуту 56 секунд работы, а в случае с перестройкой дерева — 2 минуты 1 секунду. Здесь в свою очередь разница не значительна.

Спасибо за внимание тем, кто добрался до конца моей первой статьи. Надеюсь она принесет вам пользу, мне уж точно принесла. Всем добра