from IPython.display import display, Math, Latex
from IPython.core.display import HTML
Обучение на ассоциативных правилах (далее Associations rules learning - ARL) представляет из себя с одной стороны, простой, с другой - довольно часто применимый в реальной жизни метод поиска взаимосвязей (ассоциаций) в датасетах или, если точнее, айтемсетах (itemsests). Впервые подробно об этом заговорил Piatesky-Shapiro G [1] в работе “Discovery, Analysis, and Presentation of Strong Rules.” (1991) Более подробо тему развивали Agrawal R, Imielinski T, Swami A в работах “Mining Association Rules between Sets of Items in Large Databases” (1993) [2] и “Fast Algorithms for Mining Association Rules.” (1994) [3].
В общем виде ARL можно описать как "Who bought x also bought y" ("Кто купил x, также купил y"). В основе лежит анализ транзакций (transactions), внутри каждой из которых лежит свой уникальный itemset из набора items. При помощи ARL алогритмов нахоядтся те самые "правила" совпадения items внутри одной транзакции, которые потом сортируются по их силе.
Да, вот все так просто и логично.
За этой простотой, однако, могут скрываться поразительные вещи, о которых common sense даже не подозревал:)
Классический случай такого когнитивного диссонанса описан в статье D.J. Power "Ask Dan!", опубликованной в DSSResources.com [4]:
В 1992 году группа по консалтингу в области ритейла компании Teradata под руководством Томаса Блишока провела исследование 1.2 миллиона транзакций в 25 магазинах для ритейлера Osco Drug (нет, там продавали не наркотики и даже не лекарства, точнее, не только лекартсва. Drug Store в стране вероятного противника - формат разнокалиберных магазинов у дома). После анализа всех этих транзакций самым сильным правилом получилось "Между 17:00 и 19:00 чаще всего пиво и подгузники покупают вместе". К сожалению такое правило показалось руководству Osco Drug настолько контринтуитивным, что ставить подгузники на полках рядом с пивом они не стали:) Хотя объяснение паре пиво-подгузники вполне себе нашлось: когда оба члена молодой семьи возвращались с работы домой (как раз часам к 5 вечера), жены обычно отправляли мужей за подгузниками в ближайший магазин. И мужья, не долго думая, совмещали приятное с полезным - покупали подгузники по заданию жены и пиво для собственного вечернего времяпрепровождения
Итак мы выяснили, что пиво и подгузники - хороший джентельменский набор, а что дальше?
Пусть у нас имеется некий датасет (или коллекция) D, такой, что D = {d_0 ... d_j}, где d - уникальная транзакция-itemset (например, кассовый чек). Внутри каждой d представлен набор items (i - item), причем в идеальном случае он представлен в бинарном виде: d1 = [{Пиво: 1}, {Вода: 0}, {Кола: 1}, {...}], d2 = [{Пиво : 0}, {Вода: 1}, {Кола : 1}, {...}]. Принято каждый itemset описывать через количество ненулевых значений (k-itemset), например, [{Пиво: 1}, {Вода: 0}, {Кола: 1}] является 2-itemset.
Если в изначальном виде не представлен, можно при желании руками его преобразовать (OHE и pd.get_dummies вам в помощь).
Таким образом, датасет представляет собой разреженную матрицу со значениями {1,0}. Это будет бинарный датасет. Существуют и другие виды записи - вертикальный датасет (показывает для каждого отдельного item вектор транзакций, где он присутствует) и транзакционный датасет (примерно как в кассовом чеке).
ОК, данные преобразовали, как найти правила?
Существует целый ряд ключевых (если хотите - базовых) понятий в ARL, которые нам помогут эти правила вывести.
Первое понятие в ARL - support:
$supp(X) = \frac{\{t\in T;\ X \in t\}}{|T|}$
, где X - itemset, содержащий в себе i-items, а T - количество транзакций. Т.е. в общем виде это показатель "частотности" данного itemset во всех анализируемых транзакциях. Но это касается только X. Нам же интересен скорее вариант, когда у нас в одном itemset встречаются x1 и x2 (например). Ну тут тоже все просто. Пусть x1 = {Пиво}, а x2 = {Подгузники}, значит нам нужно посчитать, во скольких транзакциях втречается эта парочка.
$supp(x_1\cup x_2) = \frac{\sigma(x_1 \cup x_2)}{|T|}$, где $\sigma $ - количество транзакций, содержащих $x_1$ и $x_2$
Разберемся с этим понятием на игрушечном датасете
play_set = pd.read_csv('data/play_set.csv', sep = ';')
play_set
# микродатасет, где указаны номера транзакций, а также в бинарном виде представлено, что покупалось на каждой транзакции
Transaction | Пиво | Подгузники | Кола | |
---|---|---|---|---|
0 | 1 | 1 | 1 | 1 |
1 | 2 | 0 | 1 | 0 |
2 | 3 | 1 | 0 | 1 |
3 | 4 | 1 | 0 | 1 |
4 | 5 | 1 | 1 | 0 |
$supp = \frac{\text{Транзакции с пивом и подгузниками}}{\text{Все транзакции}}$ = $P(\text{Пиво}\cap\text{Подгузники})$
$supp = \frac{2}{5}$ = 40%
Следующее ключевое понятие - confidence. Это показатель того, как часто наше правило срабатывает для всего датасета.
$conf(x_1\cup x_2) = \frac{supp(x_1 \cup x_2)}{supp(x_1)}$
Приведем пример: мы хотим посчитать confidence для правила "кто покупает пиво, тот покупает и подгузники".
Для этого сначала посчитаем, какой support у правила "покупает пиво", потом посчитаем support у правила "покупает пиво и подгузники", и просто поделим одно на другое. Т.е. мы посчитаем в скольких случаях (транзакциях) срабатывает правило "купил пиво $supp(X)$, купил подгузники и пиво $supp(X \cup Y)$" Ничего не напоминает? Байес смотрит на все это несколько недоуменно и с презрением:)
Посмотрим на нашем микродатасете
$conf(\text{Пиво}\cup \text{Подгузники}) = \frac{supp(\text{Пиво}\cup \text{Подгузники})}{supp(\text{Подгузники})}$ = $P(\text{Пиво}\mid\text{Подгузники})$
$conf = \frac{2}{3}$ = 67%
Следующее понятие в нашем списке - lift. Грубо говоря, lift - это отношение "зависимости" items к их "независимости". Lift показывает, насколько items зависят друг от друга. Это очевидно из формулы:
$lift(x_1\cup x_2) = \frac{supp(x_1 \cup x_2)}{supp(x_1) \times supp(x_2)}$
Например, мы хотим понять зависимость покупки пива и покупки подгузников. Для этого считаем support правила "купил пиво и подгузники" и делим его на произведение правил "купил пиво" и "купил подгузники". В случае, если lift = 1, мы говорим, что items независимы и правил совместной покупки тут нет. Если же lift > 1, то величина, на которую lift, собственно, больше этой самой единицы, и покажет нам "силу" правила. Чем больше единицы, тем круче. По-другому lift можно определить как отношение confidence к expected confidence, т.е. отношение достоверности правила, когда оба (ну или сколько там захотите) элемента покупаются вместе к достоверности правила, когда один из элементов покупался (неважно, со вторым или без)
$lift = \frac{\text{Confidence}}{\text{Expected confidence}}$ = $\frac{P(\text{Пиво} \mid \text{Подгузники})}{P(\text{Подгузники})}$
$lift = \frac{\frac{2}{3}}{\frac{3}{5}}$ = 1,(11)
Т.е. наше правило, что пиво покупают с подгузникми, на 11% мощнее правила, что подгузники просто покупают
В общем виде Conviction - это "частотность ошибок" нашего правила. Т.е., например, как часто покупали пиво без подгузников и наоборот.
$conv(x_1\cup x_2) = \frac{1 - supp(x_2)}{1 - conf(x_1 \cup x_2)}$
$conv(\text{Пиво}\cup \text{Подгузники} ) = \frac{1 - supp(\text{Подгузники})}{1 - conf(\text{Пиво} \cup \text{Подгузники})}$ = $\frac{1 - 0.4}{1 - 0.67}$ = $1,(81)$
Чем результат по формуле выше ближе к 1, тем лучше. Например, если conviction покупки пива и подгузников вместе был бы равен 1.2, это значит, что правило "купил пиво и подгузники" было бы в 1.2 раза (на 20%) более верным, чем если бы совпадение этих items в одной транзакции было бы чисто случайным. Немного не интуитивное понятие, но оно и используется не так часто, как предыдущие три.
Существует ряд часто используемых классических алгоритмов, позволяющих находить правила в itemsets согласно перечисленным выше понятиям - Наивный или брутфорс-алгоритм, Apriori- алгоритм, ECLAT-алгоритм, FP-growth алгоритм и другие.
Найти правила в itemsets в общем не сложно, сложно сделать это эффективно. Брутфорс-алгоритм самый простой и, в то же время, самый неэффективный способ.
В псевдо-коде алгоритм выглядит так:
ВХОД: Датасет $D$, содержащий список транзакций
ВЫХОД: Наборы itemsets $F_1, F_2, F_3, ... F_q$, где $F_i$ - набор itemsets размера $I$, которые встречаются как минимум $s$ раз в $D$
ПОДХОД:
Сложность брутфорс-алгоритма очевидна: Для того чтобы найти все возможные Association rules применяя брутфорс-алгоритм нам необходимо перечислить все подмножества $X$ из набора $I$ и для каждого подмножества $X$ рассчитать $supp(X)$. Данный подход будет состоять из следующих шагов:
Таким образом, сложность нашего алгоритма будет: $O(|I|*|D|*2^{|I|})$, где
$O(2^{|I|})$ - количество возможных кандидатов
$O(|I|*|D|)$ - сложность расчета $supp(X)$, поскольку для расчета $supp(X)$ нам необходимо перебрать все элементы в $I$ в каждой транзакции $t \in T$
В нотации O-большое нам понадобится $O(N)$ операций, где $N$ - количество itemsets.
Таким образом, для применения брутфорс-алгоритма нам понадобится $2^i$ ячеек памяти, где $i$ - индивидуальный itemset. Т.е. для хранения и обсчета 34 items нам понадобится 128GB RAM (для 64-битных целосчисленных ячеек).
Таким образом брутфорс поможет нам в обсчете транзакций в палатке с шаурмой у вокзала, но для чего-то более серьезного он совершенно не пригоден.
Используемые понятия:
- Множество объектов (itemset): $X \subseteq I = \{x_1, x_2, ..., x_n\}$
- Множество идентификаторов транзакций (tidset): $T = \{t_1, t_2, ..., t_m\}$
- Множество транзакций (transactions): $\{(t,\ X):\ t\in T,\ X \in I\}$
Введем дополнительно еще несколько понятий.
Будем рассматривать дерево префиксов (prefix tree), где 2 элемента $X$ и $Y$ соединены, если $X$ является прямым подмножеством $Y$. Таким образом мы можем пронумеровать все подмножества множества $I$. Рисунок приведен ниже
Итак, рассмотрим Apriori алгоритм.
Apriori алгоритм по-уровнево проходит по префиксному дереву и рассчитывает частоту встречаемости подмножеств $X$ в $D$. Таким образом, в соответствии с алгоритмом:
В псевдо-код нотации Априори-алгоритм выглядит следующим образом:
ВХОД: Датасет $D$, содержащий список транзакций, и $\sigma$ - задаваемый пользователем порог $supp$
ВЫХОД: Список itemsets $F(D, \sigma)$
ПОДХОД:
Таким образом, Apriori-алгоритм сначала ищет все единичные (содержащие 1 элемент) itemsets, удовлетворяющие заданному пользователем $supp$, затем составляет из них пары по принципу иерархической монотонности, т.е. если $x_1$ встречается часто и $x_2$ встречается часто, то и $[x_1, x_2]$ встречается часто.
Явным минусом такого подхода является то, что необходимо "просканировать" весь датасет, посчитать все $supp$ на всех уровнях breadth-first search (поиск в ширину - подробнее тут) Это также может подъесть RAM на больших датасетах, хотя и намного эффективнее брутфорса
from sklearn import... эммм... а импортировать-то и нечего:) На данный момент модулей для ALR в sklearn нет. Ну ничего, погуглим или напишем свои, правда?
Мы же на практике придерживаемся алгоритма apyori, написанного Ю Мочиузки (Yu Mochizuki). Полный код приводить не будем, желающие могут посмотреть тут , а вот архитектуру решения и пример использования покажем.
Условно решение Мочизуки можно разделить на 4 части: Структура данных, Внутренние функции, API и Прикладные функции.
Первая часть модуля (Структура данных) работает с изначальным датасетом. Реализуется класс TransactionManager, методы которого объединяют транзакции в матрицу, формируют список правил-кандидатов и считают support для каждого правила. Внутренние функции дополнительно по support'у формируют списки правил и соответственно их ранжируют. API логично позволяет работать напрямую с датасетами, а Прикладные функции позволяют обрабатывать транзакции и выводить результат в читаемый вид. Никакого rocketscience.
Посмотрим, как использовать модуль на реальном (ну, в данном случае - игрушечном) датасете.
# подгрузим модули
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
# загрузим данные
dataset = pd.read_csv('data/Market_Basket_Optimisation.csv', header = None)
# посомтрим на датасет
dataset.head()
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | shrimp | almonds | avocado | vegetables mix | green grapes | whole weat flour | yams | cottage cheese | energy drink | tomato juice | low fat yogurt | green tea | honey | salad | mineral water | salmon | antioxydant juice | frozen smoothie | spinach | olive oil |
1 | burgers | meatballs | eggs | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
2 | chutney | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
3 | turkey | avocado | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
4 | mineral water | milk | energy bar | whole wheat rice | green tea | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN | NaN |
dataset.fillna(method = 'ffill',axis = 1, inplace = True)
Видим, что датасет у нас представляет разреженную матрицу, где в строках у нас набор items в каждой транзакции.
dataset.head()
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | shrimp | almonds | avocado | vegetables mix | green grapes | whole weat flour | yams | cottage cheese | energy drink | tomato juice | low fat yogurt | green tea | honey | salad | mineral water | salmon | antioxydant juice | frozen smoothie | spinach | olive oil |
1 | burgers | meatballs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs | eggs |
2 | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney | chutney |
3 | turkey | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado | avocado |
4 | mineral water | milk | energy bar | whole wheat rice | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea | green tea |
#создаим из них матрицу
transactions = []
for i in range(0, 7501):
transactions.append([str(dataset.values[i,j]) for j in range(0, 20)])
#загружаем apriori
import apriori
%%time
# и обучимся правилам. Обратите внимание, что пороговые значения мы вибираем сами в зависимости от того,
# насколкьо "сильные" правила мы хотим получить
# min_support -- минимальный support для правил (dtype = float).
# min_confidence -- минимальное значение confidence для правил (dtype = float)
# min_lift -- минимальный lift (dtype = float)
# max_length -- максимальная длина itemset (вспоминаем про k-itemset) (dtype = integer)
result = list(apriori.apriori(transactions, min_support = 0.003, min_confidence = 0.2, min_lift = 4, min_length = 2))
Wall time: 504 ms
Визуализируем выход
import shutil, os
try:
from StringIO import StringIO
except ImportError:
from io import StringIO
import json #преобразовывать будем в json, используя встроенные в модуль методы
output = []
for RelationRecord in result:
o = StringIO()
apriori.dump_as_json(RelationRecord, o)
output.append(json.loads(o.getvalue()))
data_df = pd.DataFrame(output)
# и взгялнем на итоги
pd.set_option('display.max_colwidth', -1)
from IPython.display import display, HTML
display(HTML(data_df.to_html()))
items | ordered_statistics | support | |
---|---|---|---|
0 | [chicken, light cream] | [{'items_base': ['light cream'], 'items_add': ['chicken'], 'confidence': 0.29059829059829057, 'lift': 4.84395061728395}] | 0.004533 |
1 | [escalope, pasta] | [{'items_base': ['pasta'], 'items_add': ['escalope'], 'confidence': 0.3728813559322034, 'lift': 4.700811850163794}] | 0.005866 |
2 | [fromage blanc, honey] | [{'items_base': ['fromage blanc'], 'items_add': ['honey'], 'confidence': 0.2450980392156863, 'lift': 5.164270764485569}] | 0.003333 |
3 | [olive oil, whole wheat pasta] | [{'items_base': ['whole wheat pasta'], 'items_add': ['olive oil'], 'confidence': 0.2714932126696833, 'lift': 4.122410097642296}] | 0.007999 |
4 | [pasta, shrimp] | [{'items_base': ['pasta'], 'items_add': ['shrimp'], 'confidence': 0.3220338983050847, 'lift': 4.506672147735896}] | 0.005066 |
5 | [cake, frozen vegetables, tomatoes] | [{'items_base': ['cake', 'frozen vegetables'], 'items_add': ['tomatoes'], 'confidence': 0.2987012987012987, 'lift': 4.367560314928736}] | 0.003066 |
6 | [cereals, ground beef, spaghetti] | [{'items_base': ['cereals', 'spaghetti'], 'items_add': ['ground beef'], 'confidence': 0.45999999999999996, 'lift': 4.681763907734057}] | 0.003066 |
7 | [chocolate, ground beef, herb & pepper] | [{'items_base': ['chocolate', 'herb & pepper'], 'items_add': ['ground beef'], 'confidence': 0.4411764705882354, 'lift': 4.4901827759597746}] | 0.003999 |
8 | [eggs, ground beef, herb & pepper] | [{'items_base': ['eggs', 'ground beef'], 'items_add': ['herb & pepper'], 'confidence': 0.2066666666666667, 'lift': 4.178454627133872}] | 0.004133 |
9 | [french fries, ground beef, herb & pepper] | [{'items_base': ['french fries', 'ground beef'], 'items_add': ['herb & pepper'], 'confidence': 0.23076923076923078, 'lift': 4.665768194070081}, {'items_base': ['french fries', 'herb & pepper'], 'items_add': ['ground beef'], 'confidence': 0.46153846153846156, 'lift': 4.697421981004071}] | 0.003200 |
10 | [ground beef, herb & pepper, spaghetti] | [{'items_base': ['herb & pepper', 'spaghetti'], 'items_add': ['ground beef'], 'confidence': 0.3934426229508197, 'lift': 4.004359721511667}] | 0.006399 |
11 | [ground beef, spaghetti, tomato sauce] | [{'items_base': ['spaghetti', 'tomato sauce'], 'items_add': ['ground beef'], 'confidence': 0.4893617021276596, 'lift': 4.980599901844742}] | 0.003066 |
12 | [milk, olive oil, soup] | [{'items_base': ['milk', 'olive oil'], 'items_add': ['soup'], 'confidence': 0.2109375, 'lift': 4.174781497361478}] | 0.003600 |
13 | [milk, soup, tomatoes] | [{'items_base': ['milk', 'tomatoes'], 'items_add': ['soup'], 'confidence': 0.21904761904761905, 'lift': 4.335293378565146}] | 0.003066 |
14 | [mineral water, olive oil, whole wheat pasta] | [{'items_base': ['mineral water', 'whole wheat pasta'], 'items_add': ['olive oil'], 'confidence': 0.4027777777777778, 'lift': 6.115862573099416}] | 0.003866 |
15 | [chocolate, frozen vegetables, mineral water, shrimp] | [{'items_base': ['chocolate', 'frozen vegetables', 'mineral water'], 'items_add': ['shrimp'], 'confidence': 0.32876712328767127, 'lift': 4.600899611531385}, {'items_base': ['chocolate', 'mineral water', 'shrimp'], 'items_add': ['frozen vegetables'], 'confidence': 0.4210526315789474, 'lift': 4.417224880382776}] | 0.003200 |
16 | [frozen vegetables, milk, mineral water, olive oil] | [{'items_base': ['frozen vegetables', 'milk', 'mineral water'], 'items_add': ['olive oil'], 'confidence': 0.30120481927710846, 'lift': 4.573557387444516}, {'items_base': ['milk', 'mineral water', 'olive oil'], 'items_add': ['frozen vegetables'], 'confidence': 0.39062500000000006, 'lift': 4.098011363636364}] | 0.003333 |
17 | [frozen vegetables, milk, mineral water, soup] | [{'items_base': ['frozen vegetables', 'milk', 'mineral water'], 'items_add': ['soup'], 'confidence': 0.27710843373493976, 'lift': 5.484407286136631}, {'items_base': ['frozen vegetables', 'mineral water', 'soup'], 'items_add': ['milk'], 'confidence': 0.6052631578947368, 'lift': 4.670863114576565}] | 0.003066 |
18 | [frozen vegetables, mineral water, shrimp, spaghetti] | [{'items_base': ['mineral water', 'shrimp', 'spaghetti'], 'items_add': ['frozen vegetables'], 'confidence': 0.39062500000000006, 'lift': 4.098011363636364}] | 0.003333 |
Итого мы видим:
Результаты логичные: эскалоп и макароны, эскалоп и сливочно-грибной соус, курица и нежирная сметана, мягкий сыр и мед и т.д. - все это вполне логичные и, главное, вкусные сочетания:)
ARL тот случай,скогда R-филы могут злорадно похихикать (java-филы вообще смотрят на нас смертных с презрением, но об этом ниже). В R реализована библиотека arules, где присутствует и apriori, и другие алгоритмы. Официальную доку можно посмотреть тут
Посмотрим на нее в действии:
Для начала установим ее (если еще не установили):
Считаем данные и преобразуем их в матрицу транзакций:
Посмотрим на данные:
Выучим наши правила:
$data$ - наш датасет
Обучим модель:
$rules = apriori(data = dataset, parameter = list(support = 0.004, confidence = 0.2))$
И посмотрим на результаты:
Убедимся, что на выходе имеем примерно те же результаты, что при использовании модуля apyori в Python:
Как видно, в R apriori использовать на данный момент намного удобнее, чем в Python.
Идея алгоритма ECLAT (Equivalence CLAss Transformation) заключается в ускорении подсчета $supp(X)$. Для этого нам необходимо проиндексировать нашу базу данных $D$ так, чтобы это позволило быстро рассчитывать $supp(X)$
Легко заметить, что если $t(X)$ обозначает множество всех транзакций, где встречается подмножество $X$, то
$t(XY) = t(X) \cap t(Y)$
и
$supp(XY) = |t(XY)|$
то есть $supp(XY)$ равен кардинальности (размеру) множества $t(XY)$
Данный подход может быть значительно усовершенствован путем уменьшения размера промежуточных множеств идентификаторов транзакций (tidsets). А именно, мы можем хранить не все множество транзакций на промежуточном уровне, а только множество различий этих транзакций. Предположим, что
$X_a = \{x_1, x_2,..., x_{n-1}, a\}$
$X_b = \{x_1, x_2,..., x_{n-1}, b\}$
Тогда, мы получим:
$X_{ab} = \{x_1, x_2,..., x_{n-1}, a, b\}$
$diffset(X_{ab})$ это множество всех id транзакций, которые содержат префикс $X_a$ но не содержат элемент $b$:
$d(X_{ab}) =t(X_a)/t(X_{ab})=t(X_a)/t(X_{b})$
В отличие от Apriori-алгоритма, ECLAT производит поиск в глубину (DFS, подробнее тут). Иногда его называют "вертикальным" (в отличие от "горизонтального" для Apriori)
ВХОД: Датасет $D$, содержащий список транзакций, $\sigma$ - задаваемый пользователем порог $supp$ и новый элемент префикс $I \subseteq J$
ВЫХОД: Список itemsets $F[I](D, \sigma)$ для соответсвующего префикса $I$
ПОДХОД:
Ключевым понятием для ECLAT-алгоритма является I-префикс. В началае генерируется пустое множество I, это позволяет нам на первом проходе выделить все частотные itemsets. Затем алгоритм будет вызывать сам себя и увеличивать I на 1 на каждом шаге до тех пор, пока не будет достигнута заданная пользователем длина I.
Для хранения значений используется префиксное дерево (trie (не tree:)), тут подробнее). Вначале строится нулевой корень дерева (то самое пустое множество I), затем по мере прохода по itemsets алгоритм прописывает содержащиеся в каждом itesmsets items, при этом самая левая ветвь является child нулевого корня и далее вниз. При этом ветвей столько, сколкьо items встречаестя в itemsets. Такой подход позволяет записывать itemset в памяти только один раз, что делает ECALT быстрее Apriori.
Существует несколько реализаций данного алгоритма в Python, желающие могут погуглить и даже попытаться их заставить работать, но мы же напишем свой, максимально простой и, главное, рабочий:)
import numpy as np
"""
Класс инициируется 3мя параметрами:
- min_supp - минимальный support который мы рассматриваем для ItemSet. Рассчитывается как % от количества транзакций
- max_items - максимальное количество елементов в нашем ItemSet
- min_items - минимальное количество элементов ItemSet
"""
class Eclat:
#инициализация объекта класса
def __init__(self, min_support = 0.01, max_items = 5, min_items = 2):
self.min_support = min_support
self.max_items = max_items
self.min_items = min_items
self.item_lst = list()
self.item_len = 0
self.item_dict = dict()
self.final_dict = dict()
self.data_size = 0
#создание словаря из ненулевых объектов из всех транзакций (вертикальный датасет)
def read_data(self, dataset):
for index, row in dataset.iterrows():
row_wo_na = set(row[0])
for item in row_wo_na:
item = item.strip()
if item in self.item_dict:
self.item_dict[item][0] += 1
else:
self.item_dict.setdefault(item, []).append(1)
self.item_dict[item].append(index)
#задаем переменные экземпляра (instance variables)
self.data_size = dataset.shape[0]
self.item_lst = list(self.item_dict.keys())
self.item_len = len(self.item_lst)
self.min_support = self.min_support * self.data_size
#print ("min_supp", self.min_support)
#рекурсивный метод для поиска всех ItemSet по алгоритму Eclat
#структура данных: {Item: [Supp number, tid1, tid2, tid3, ...]}
def recur_eclat(self, item_name, tids_array, minsupp, num_items, k_start):
if tids_array[0] >= minsupp and num_items <= self.max_items:
for k in range(k_start+1, self.item_len):
if self.item_dict[self.item_lst[k]][0] >= minsupp:
new_item = item_name + " | " + self.item_lst[k]
new_tids = np.intersect1d(tids_array[1:], self.item_dict[self.item_lst[k]][1:])
new_tids_size = new_tids.size
new_tids = np.insert(new_tids, 0, new_tids_size)
if new_tids_size >= minsupp:
if num_items >= self.min_items: self.final_dict.update({new_item: new_tids})
self.recur_eclat(new_item, new_tids, minsupp, num_items+1, k)
#последовательный вызов функций определенных выше
def fit(self, dataset):
i = 0
self.read_data(dataset)
for w in self.item_lst:
self.recur_eclat(w, self.item_dict[w], self.min_support, 2, i)
i+=1
return self
#вывод в форме словаря {ItemSet: support(ItemSet)}
def transform(self):
return {k: "{0:.4f}%".format((v[0]+0.0)/self.data_size*100) for k, v in self.final_dict.items()}
Потестируем
#создадим экземпляр класса с нужными нам параметрами
model = Eclat(min_support = 0.01, max_items = 4, min_items = 3)
#обучим
model.fit(dataset)
<__main__.Eclat at 0x224ff5bd240>
#и визуализируем результаты
model.transform()
{'eggs | spaghetti | chocolate': '1.0532%', 'milk | spaghetti | chocolate': '1.0932%', 'mineral water | chocolate | ground beef': '1.0932%', 'mineral water | eggs | chocolate': '1.3465%', 'mineral water | eggs | ground beef': '1.0132%', 'mineral water | eggs | milk': '1.3065%', 'mineral water | eggs | spaghetti': '1.4265%', 'mineral water | french fries | spaghetti': '1.0132%', 'mineral water | frozen vegetables | spaghetti': '1.1998%', 'mineral water | milk | chocolate': '1.3998%', 'mineral water | milk | frozen vegetables': '1.1065%', 'mineral water | milk | ground beef': '1.1065%', 'mineral water | milk | spaghetti': '1.5731%', 'mineral water | olive oil | spaghetti': '1.0265%', 'mineral water | spaghetti | chocolate': '1.5865%', 'mineral water | spaghetti | ground beef': '1.7064%', 'mineral water | spaghetti | pancakes': '1.1465%'}
Итак, алгоритм работает. Но так ли он применим в реальной жизни? Давайте проверим.
Есть реальная бизнес задача , которая поступила нам от крупного продуктового ритейлера премиум-сегмента (раскрывать название не будем, корпоративная тайна-с): посмотреть те самые наиболее частые наборы в продуктовых корзинах.
Загрузим данные из выгрузки из POS-ситемы (Point-of-Sale - система, обрабатывающая транзакции на кассах)
Загрузим данные
df = pd.read_csv('data/tranprod1.csv', delimiter = ';', header = 0)
df.columns = ['trans', 'item']
print(df.shape)
df.head()
(851083, 2)
/home/bashnick/anaconda3/lib/python3.6/site-packages/IPython/core/interactiveshell.py:2728: DtypeWarning: Columns (0) have mixed types. Specify dtype option on import or set low_memory=False. interactivity=interactivity, compiler=compiler, result=result)
trans | item | |
---|---|---|
0 | 284340645 | ТОВ255868 |
1 | 284340942 | ТОВ219972 |
2 | 284340942 | ТОВ256924 |
3 | 284342046 | ТОВ251559 |
4 | 284343063 | ТОВ225352 |
Поменяем формат таблицы на "транзакция | список" всех item в транзакции
df.trans = pd.to_numeric(df.trans, errors='coerce')
df.dropna(axis = 0, how = 'all', inplace = True)
df.trans = df.trans.astype(int)
df = df.groupby('trans').agg(lambda x: x.tolist())
df.head()
item | |
---|---|
trans | |
284339008 | [ТОВ276911, ТОВ088835, ТОВ042562, ТОВ109423, Т... |
284339009 | [ТОВ004568, ТОВ141629, ТОВ164029, ТОВ218562, Т... |
284339010 | [ТОВ246052, ТОВ231590, ТОВ242527, ТОВ234309] |
284339011 | [ТОВ206914, ТОВ153118, ТОВ208685, ТОВ042960, Т... |
284339012 | [ТОВ231586] |
Запустим алгоитм
model = Eclat(min_support = 0.0001, max_items = 4, min_items = 3)
%%time
model.fit(df)
Data read successfully min_supp 9.755 CPU times: user 6h 47min 9s, sys: 22.2 s, total: 6h 47min 31s Wall time: 6h 47min 28s
<my_eclat.Eclat at 0x7f19829d6fd0>
d = model.transform()
d
{'ТОВ009894 | ТОВ231586 | ТОВ184253': '0.0154%', 'ТОВ009894 | ТОВ231586 | ТОВ232715': '0.0154%', 'ТОВ009894 | ТОВ215649 | ТОВ232715': '0.0113%', 'ТОВ009894 | ТОВ224330 | ТОВ170478': '0.0154%', 'ТОВ009894 | ТОВ184253 | ТОВ139528': '0.0246%', 'ТОВ009894 | ТОВ184253 | ТОВ262977': '0.0103%', 'ТОВ009894 | ТОВ184253 | ТОВ232715': '0.0246%', 'ТОВ009894 | ТОВ184253 | ТОВ227714': '0.0123%', 'ТОВ009894 | ТОВ184253 | ТОВ170478': '0.0113%', 'ТОВ009894 | ТОВ184253 | ТОВ155841': '0.0113%', 'ТОВ009894 | ТОВ184253 | ТОВ255036': '0.0123%', 'ТОВ009894 | ТОВ184253 | ТОВ043107': '0.0123%', 'ТОВ009894 | ТОВ184253 | ТОВ052777': '0.0113%', 'ТОВ009894 | ТОВ184253 | ТОВ097249': '0.0133%', 'ТОВ009894 | ТОВ184253 | ТОВ032043': '0.0113%', 'ТОВ009894 | ТОВ139528 | ТОВ255036': '0.0123%', 'ТОВ009894 | ТОВ139528 | ТОВ032043': '0.0103%', 'ТОВ009894 | ТОВ142564 | ТОВ178947': '0.0113%', 'ТОВ009894 | ТОВ142564 | ТОВ178947 | ТОВ162300': '0.0103%', 'ТОВ009894 | ТОВ142564 | ТОВ162300': '0.0103%', 'ТОВ009894 | ТОВ232715 | ТОВ170478': '0.0174%', 'ТОВ009894 | ТОВ232715 | ТОВ097249': '0.0144%', 'ТОВ009894 | ТОВ227714 | ТОВ227717': '0.0133%', 'ТОВ009894 | ТОВ178947 | ТОВ162300': '0.0103%', 'ТОВ231432 | ТОВ228114 | ТОВ166306': '0.0133%', 'ТОВ231432 | ТОВ228114 | ТОВ184253': '0.0215%', 'ТОВ231432 | ТОВ228114 | ТОВ139528': '0.0113%', 'ТОВ231432 | ТОВ228114 | ТОВ262977': '0.0144%', 'ТОВ231432 | ТОВ228114 | ТОВ235739': '0.0103%', 'ТОВ231432 | ТОВ228114 | ТОВ227715': '0.0185%', 'ТОВ231432 | ТОВ228114 | ТОВ230700': '0.0113%', 'ТОВ231432 | ТОВ228114 | ТОВ043107': '0.0103%', 'ТОВ231432 | ТОВ228114 | ТОВ097249': '0.0123%', 'ТОВ231432 | ТОВ279361 | ТОВ184253': '0.0103%', 'ТОВ231432 | ТОВ279361 | ТОВ232715': '0.0113%', 'ТОВ231432 | ТОВ279361 | ТОВ255036': '0.0103%', 'ТОВ231432 | ТОВ033048 | ТОВ184253': '0.0113%', 'ТОВ231432 | ТОВ033048 | ТОВ227714': '0.0123%', 'ТОВ231432 | ТОВ033048 | ТОВ227717': '0.0133%', 'ТОВ231432 | ТОВ166306 | ТОВ139528': '0.0195%', 'ТОВ231432 | ТОВ166306 | ТОВ053041': '0.0103%', 'ТОВ231432 | ТОВ166306 | ТОВ227714': '0.0133%', 'ТОВ231432 | ТОВ166306 | ТОВ227715': '0.0113%', 'ТОВ231432 | ТОВ166306 | ТОВ155841': '0.0103%', 'ТОВ231432 | ТОВ166306 | ТОВ227717': '0.0144%', 'ТОВ231432 | ТОВ224035 | ТОВ184253': '0.0113%', 'ТОВ231432 | ТОВ184253 | ТОВ263281': '0.0113%', 'ТОВ231432 | ТОВ184253 | ТОВ139528': '0.0195%', 'ТОВ231432 | ТОВ184253 | ТОВ262977': '0.0164%', 'ТОВ231432 | ТОВ184253 | ТОВ232715': '0.0123%', 'ТОВ231432 | ТОВ184253 | ТОВ042704': '0.0113%', 'ТОВ231432 | ТОВ184253 | ТОВ283493': '0.0103%', 'ТОВ231432 | ТОВ184253 | ТОВ042547': '0.0144%', 'ТОВ231432 | ТОВ184253 | ТОВ227714': '0.0236%', 'ТОВ231432 | ТОВ184253 | ТОВ227715': '0.0185%', 'ТОВ231432 | ТОВ184253 | ТОВ155841': '0.0123%', 'ТОВ231432 | ТОВ184253 | ТОВ255036': '0.0174%', 'ТОВ231432 | ТОВ184253 | ТОВ227717': '0.0195%', 'ТОВ231432 | ТОВ184253 | ТОВ227716': '0.0103%', 'ТОВ231432 | ТОВ184253 | ТОВ043107': '0.0113%', 'ТОВ231432 | ТОВ184253 | ТОВ237675': '0.0103%', 'ТОВ231432 | ТОВ184253 | ТОВ097249': '0.0113%', 'ТОВ231432 | ТОВ184253 | ТОВ032043': '0.0164%', 'ТОВ231432 | ТОВ139528 | ТОВ042547': '0.0103%', 'ТОВ231432 | ТОВ139528 | ТОВ227714': '0.0174%', 'ТОВ231432 | ТОВ139528 | ТОВ099797': '0.0113%', 'ТОВ231432 | ТОВ139528 | ТОВ227715': '0.0103%', 'ТОВ231432 | ТОВ139528 | ТОВ227717': '0.0144%', 'ТОВ231432 | ТОВ139528 | ТОВ237675': '0.0113%', 'ТОВ231432 | ТОВ139528 | ТОВ032043': '0.0123%', 'ТОВ231432 | ТОВ262977 | ТОВ227717': '0.0144%', 'ТОВ231432 | ТОВ262977 | ТОВ043107': '0.0123%', 'ТОВ231432 | ТОВ262977 | ТОВ237675': '0.0103%', 'ТОВ231432 | ТОВ262977 | ТОВ032043': '0.0103%', 'ТОВ231432 | ТОВ232715 | ТОВ227714': '0.0103%', 'ТОВ231432 | ТОВ232715 | ТОВ255036': '0.0113%', 'ТОВ231432 | ТОВ232715 | ТОВ043107': '0.0103%', 'ТОВ231432 | ТОВ193716 | ТОВ230700': '0.0133%', 'ТОВ231432 | ТОВ193716 | ТОВ227717': '0.0103%', 'ТОВ231432 | ТОВ193716 | ТОВ053049': '0.0103%', 'ТОВ231432 | ТОВ053041 | ТОВ227714': '0.0113%', 'ТОВ231432 | ТОВ042704 | ТОВ227714': '0.0103%', 'ТОВ231432 | ТОВ042547 | ТОВ227714': '0.0164%', 'ТОВ231432 | ТОВ042547 | ТОВ255036': '0.0113%', 'ТОВ231432 | ТОВ042547 | ТОВ227717': '0.0154%', 'ТОВ231432 | ТОВ235739 | ТОВ227714': '0.0144%', 'ТОВ231432 | ТОВ235739 | ТОВ227715': '0.0123%', 'ТОВ231432 | ТОВ235739 | ТОВ227717': '0.0113%', 'ТОВ231432 | ТОВ227714 | ТОВ227715': '0.0215%', 'ТОВ231432 | ТОВ227714 | ТОВ230700': '0.0103%', 'ТОВ231432 | ТОВ227714 | ТОВ255036': '0.0144%', 'ТОВ231432 | ТОВ227714 | ТОВ227717': '0.0297%', 'ТОВ231432 | ТОВ227714 | ТОВ227716': '0.0256%', 'ТОВ231432 | ТОВ227714 | ТОВ237675': '0.0154%', 'ТОВ231432 | ТОВ227715 | ТОВ227717': '0.0123%', 'ТОВ231432 | ТОВ227715 | ТОВ227716': '0.0113%', 'ТОВ231432 | ТОВ283303 | ТОВ227717': '0.0113%', 'ТОВ231432 | ТОВ255036 | ТОВ227717': '0.0103%', 'ТОВ231432 | ТОВ255036 | ТОВ043107': '0.0113%', 'ТОВ231432 | ТОВ227717 | ТОВ227716': '0.0144%', 'ТОВ231432 | ТОВ227717 | ТОВ043107': '0.0103%', 'ТОВ231432 | ТОВ227717 | ТОВ237675': '0.0174%', 'ТОВ231432 | ТОВ227716 | ТОВ237675': '0.0133%', 'ТОВ231432 | ТОВ237675 | ТОВ231440': '0.0113%', 'ТОВ228114 | ТОВ279361 | ТОВ231586': '0.0195%', 'ТОВ228114 | ТОВ279361 | ТОВ231586 | ТОВ184253': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ231590': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ106930': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ259350': '0.0123%', 'ТОВ228114 | ТОВ279361 | ТОВ166306': '0.0113%', 'ТОВ228114 | ТОВ279361 | ТОВ184253': '0.0543%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ139528': '0.0185%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ262977': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ232715': '0.0164%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ042547': '0.0123%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ184253 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ139528': '0.0236%', 'ТОВ228114 | ТОВ279361 | ТОВ232298': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ262977': '0.0174%', 'ТОВ228114 | ТОВ279361 | ТОВ232715': '0.0267%', 'ТОВ228114 | ТОВ279361 | ТОВ042704': '0.0144%', 'ТОВ228114 | ТОВ279361 | ТОВ042547': '0.0185%', 'ТОВ228114 | ТОВ279361 | ТОВ235739': '0.0205%', 'ТОВ228114 | ТОВ279361 | ТОВ099797': '0.0123%', 'ТОВ228114 | ТОВ279361 | ТОВ170478': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ227715': '0.0205%', 'ТОВ228114 | ТОВ279361 | ТОВ230700': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ155841': '0.0123%', 'ТОВ228114 | ТОВ279361 | ТОВ255036': '0.0185%', 'ТОВ228114 | ТОВ279361 | ТОВ227717': '0.0185%', 'ТОВ228114 | ТОВ279361 | ТОВ043107': '0.0133%', 'ТОВ228114 | ТОВ279361 | ТОВ247989': '0.0113%', 'ТОВ228114 | ТОВ279361 | ТОВ037482': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ052777': '0.0103%', 'ТОВ228114 | ТОВ279361 | ТОВ032043': '0.0174%', 'ТОВ228114 | ТОВ231586 | ТОВ109423': '0.0144%', 'ТОВ228114 | ТОВ231586 | ТОВ206304': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ231590': '0.0267%', 'ТОВ228114 | ТОВ231586 | ТОВ231590 | ТОВ232715': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ231590 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ106930': '0.0133%', 'ТОВ228114 | ТОВ231586 | ТОВ259350': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ166306': '0.0144%', 'ТОВ228114 | ТОВ231586 | ТОВ224035': '0.0144%', 'ТОВ228114 | ТОВ231586 | ТОВ184253': '0.0543%', 'ТОВ228114 | ТОВ231586 | ТОВ184253 | ТОВ139528': '0.0195%', 'ТОВ228114 | ТОВ231586 | ТОВ184253 | ТОВ262977': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ184253 | ТОВ232715': '0.0133%', 'ТОВ228114 | ТОВ231586 | ТОВ184253 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ184253 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ139528': '0.0338%', 'ТОВ228114 | ТОВ231586 | ТОВ139528 | ТОВ232715': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ139528 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ262977': '0.0215%', 'ТОВ228114 | ТОВ231586 | ТОВ232715': '0.0349%', 'ТОВ228114 | ТОВ231586 | ТОВ232715 | ТОВ042547': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ232715 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ232715 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ053041': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ231691': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ042704': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ231690': '0.0154%', 'ТОВ228114 | ТОВ231586 | ТОВ218365': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ284483': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ223175': '0.0123%', 'ТОВ228114 | ТОВ231586 | ТОВ042547': '0.0174%', 'ТОВ228114 | ТОВ231586 | ТОВ235739': '0.0154%', 'ТОВ228114 | ТОВ231586 | ТОВ222081': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ099797': '0.0154%', 'ТОВ228114 | ТОВ231586 | ТОВ227715': '0.0400%', 'ТОВ228114 | ТОВ231586 | ТОВ301624': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ249439': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ155841': '0.0144%', 'ТОВ228114 | ТОВ231586 | ТОВ042940': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ237348': '0.0133%', 'ТОВ228114 | ТОВ231586 | ТОВ178947': '0.0144%', 'ТОВ228114 | ТОВ231586 | ТОВ255036': '0.0287%', 'ТОВ228114 | ТОВ231586 | ТОВ227717': '0.0236%', 'ТОВ228114 | ТОВ231586 | ТОВ043107': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ247989': '0.0103%', 'ТОВ228114 | ТОВ231586 | ТОВ052777': '0.0113%', 'ТОВ228114 | ТОВ231586 | ТОВ098311': '0.0154%', 'ТОВ228114 | ТОВ231586 | ТОВ097249': '0.0144%', 'ТОВ228114 | ТОВ231586 | ТОВ032043': '0.0205%', 'ТОВ228114 | ТОВ219150 | ТОВ184253': '0.0113%', 'ТОВ228114 | ТОВ109423 | ТОВ238925': '0.0154%', 'ТОВ228114 | ТОВ109423 | ТОВ166306': '0.0123%', 'ТОВ228114 | ТОВ109423 | ТОВ184253': '0.0267%', 'ТОВ228114 | ТОВ109423 | ТОВ139528': '0.0185%', 'ТОВ228114 | ТОВ109423 | ТОВ262977': '0.0113%', 'ТОВ228114 | ТОВ109423 | ТОВ053041': '0.0113%', 'ТОВ228114 | ТОВ109423 | ТОВ235739': '0.0154%', 'ТОВ228114 | ТОВ109423 | ТОВ099797': '0.0113%', 'ТОВ228114 | ТОВ109423 | ТОВ227715': '0.0195%', 'ТОВ228114 | ТОВ109423 | ТОВ230700': '0.0113%', 'ТОВ228114 | ТОВ109423 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ109423 | ТОВ227717': '0.0144%', 'ТОВ228114 | ТОВ033048 | ТОВ166306': '0.0103%', 'ТОВ228114 | ТОВ033048 | ТОВ184253': '0.0215%', 'ТОВ228114 | ТОВ033048 | ТОВ139528': '0.0113%', 'ТОВ228114 | ТОВ033048 | ТОВ262977': '0.0133%', 'ТОВ228114 | ТОВ033048 | ТОВ232715': '0.0133%', 'ТОВ228114 | ТОВ033048 | ТОВ042547': '0.0103%', 'ТОВ228114 | ТОВ033048 | ТОВ235739': '0.0113%', 'ТОВ228114 | ТОВ033048 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ033048 | ТОВ227717': '0.0154%', 'ТОВ228114 | ТОВ206304 | ТОВ184253': '0.0267%', 'ТОВ228114 | ТОВ206304 | ТОВ232715': '0.0103%', 'ТОВ228114 | ТОВ206304 | ТОВ235739': '0.0113%', 'ТОВ228114 | ТОВ206304 | ТОВ227715': '0.0164%', 'ТОВ228114 | ТОВ206304 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ001465 | ТОВ184253': '0.0103%', 'ТОВ228114 | ТОВ215649 | ТОВ184253': '0.0195%', 'ТОВ228114 | ТОВ277638 | ТОВ184253': '0.0113%', 'ТОВ228114 | ТОВ238925 | ТОВ184253': '0.0103%', 'ТОВ228114 | ТОВ238925 | ТОВ227717': '0.0123%', 'ТОВ228114 | ТОВ231590 | ТОВ184253': '0.0287%', 'ТОВ228114 | ТОВ231590 | ТОВ139528': '0.0144%', 'ТОВ228114 | ТОВ231590 | ТОВ262977': '0.0144%', 'ТОВ228114 | ТОВ231590 | ТОВ232715': '0.0154%', 'ТОВ228114 | ТОВ231590 | ТОВ235739': '0.0133%', 'ТОВ228114 | ТОВ231590 | ТОВ227715': '0.0185%', 'ТОВ228114 | ТОВ231590 | ТОВ255036': '0.0164%', 'ТОВ228114 | ТОВ231590 | ТОВ227717': '0.0164%', 'ТОВ228114 | ТОВ284416 | ТОВ184253': '0.0185%', 'ТОВ228114 | ТОВ224330 | ТОВ184253': '0.0123%', 'ТОВ228114 | ТОВ120235 | ТОВ184253': '0.0205%', 'ТОВ228114 | ТОВ120235 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ120235 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ193295 | ТОВ184253': '0.0154%', 'ТОВ228114 | ТОВ193295 | ТОВ232715': '0.0113%', 'ТОВ228114 | ТОВ193295 | ТОВ042547': '0.0103%', 'ТОВ228114 | ТОВ193295 | ТОВ029305': '0.0113%', 'ТОВ228114 | ТОВ193295 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ231595 | ТОВ184253': '0.0113%', 'ТОВ228114 | ТОВ106930 | ТОВ184253': '0.0338%', 'ТОВ228114 | ТОВ106930 | ТОВ184253 | ТОВ139528': '0.0103%', 'ТОВ228114 | ТОВ106930 | ТОВ184253 | ТОВ235739': '0.0123%', 'ТОВ228114 | ТОВ106930 | ТОВ184253 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ106930 | ТОВ184253 | ТОВ255036': '0.0144%', 'ТОВ228114 | ТОВ106930 | ТОВ139528': '0.0154%', 'ТОВ228114 | ТОВ106930 | ТОВ262977': '0.0103%', 'ТОВ228114 | ТОВ106930 | ТОВ232715': '0.0164%', 'ТОВ228114 | ТОВ106930 | ТОВ053041': '0.0113%', 'ТОВ228114 | ТОВ106930 | ТОВ042547': '0.0113%', 'ТОВ228114 | ТОВ106930 | ТОВ235739': '0.0154%', 'ТОВ228114 | ТОВ106930 | ТОВ235739 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ106930 | ТОВ170478': '0.0103%', 'ТОВ228114 | ТОВ106930 | ТОВ227715': '0.0215%', 'ТОВ228114 | ТОВ106930 | ТОВ155841': '0.0103%', 'ТОВ228114 | ТОВ106930 | ТОВ255036': '0.0195%', 'ТОВ228114 | ТОВ106930 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ106930 | ТОВ032043': '0.0123%', 'ТОВ228114 | ТОВ259350 | ТОВ166306': '0.0103%', 'ТОВ228114 | ТОВ259350 | ТОВ184253': '0.0502%', 'ТОВ228114 | ТОВ259350 | ТОВ184253 | ТОВ235739': '0.0103%', 'ТОВ228114 | ТОВ259350 | ТОВ184253 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ259350 | ТОВ184253 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ259350 | ТОВ262977': '0.0113%', 'ТОВ228114 | ТОВ259350 | ТОВ232715': '0.0123%', 'ТОВ228114 | ТОВ259350 | ТОВ235739': '0.0164%', 'ТОВ228114 | ТОВ259350 | ТОВ099797': '0.0123%', 'ТОВ228114 | ТОВ259350 | ТОВ227715': '0.0205%', 'ТОВ228114 | ТОВ259350 | ТОВ230700': '0.0133%', 'ТОВ228114 | ТОВ259350 | ТОВ227717': '0.0174%', 'ТОВ228114 | ТОВ259350 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ224035': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ248429': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ184253': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ263281': '0.0123%', 'ТОВ228114 | ТОВ166306 | ТОВ139528': '0.0349%', 'ТОВ228114 | ТОВ166306 | ТОВ139528 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ232298': '0.0123%', 'ТОВ228114 | ТОВ166306 | ТОВ262977': '0.0164%', 'ТОВ228114 | ТОВ166306 | ТОВ232715': '0.0174%', 'ТОВ228114 | ТОВ166306 | ТОВ230418': '0.0113%', 'ТОВ228114 | ТОВ166306 | ТОВ053041': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ042704': '0.0154%', 'ТОВ228114 | ТОВ166306 | ТОВ042547': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ204237': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ235739': '0.0164%', 'ТОВ228114 | ТОВ166306 | ТОВ227715': '0.0349%', 'ТОВ228114 | ТОВ166306 | ТОВ230700': '0.0185%', 'ТОВ228114 | ТОВ166306 | ТОВ178947': '0.0154%', 'ТОВ228114 | ТОВ166306 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ166306 | ТОВ227717': '0.0236%', 'ТОВ228114 | ТОВ166306 | ТОВ052777': '0.0103%', 'ТОВ228114 | ТОВ166306 | ТОВ032043': '0.0123%', 'ТОВ228114 | ТОВ166306 | ТОВ129157': '0.0113%', 'ТОВ228114 | ТОВ119677 | ТОВ204237': '0.0103%', 'ТОВ228114 | ТОВ224035 | ТОВ184253': '0.0328%', 'ТОВ228114 | ТОВ224035 | ТОВ184253 | ТОВ235739': '0.0123%', 'ТОВ228114 | ТОВ224035 | ТОВ263281': '0.0103%', 'ТОВ228114 | ТОВ224035 | ТОВ139528': '0.0144%', 'ТОВ228114 | ТОВ224035 | ТОВ262977': '0.0133%', 'ТОВ228114 | ТОВ224035 | ТОВ232715': '0.0195%', 'ТОВ228114 | ТОВ224035 | ТОВ042704': '0.0123%', 'ТОВ228114 | ТОВ224035 | ТОВ042547': '0.0103%', 'ТОВ228114 | ТОВ224035 | ТОВ235739': '0.0164%', 'ТОВ228114 | ТОВ224035 | ТОВ227715': '0.0164%', 'ТОВ228114 | ТОВ224035 | ТОВ230700': '0.0174%', 'ТОВ228114 | ТОВ224035 | ТОВ255036': '0.0144%', 'ТОВ228114 | ТОВ224035 | ТОВ227717': '0.0226%', 'ТОВ228114 | ТОВ056330 | ТОВ184253': '0.0144%', 'ТОВ228114 | ТОВ056330 | ТОВ232715': '0.0103%', 'ТОВ228114 | ТОВ248429 | ТОВ184253': '0.0359%', 'ТОВ228114 | ТОВ248429 | ТОВ184253 | ТОВ232715': '0.0123%', 'ТОВ228114 | ТОВ248429 | ТОВ184253 | ТОВ042547': '0.0123%', 'ТОВ228114 | ТОВ248429 | ТОВ184253 | ТОВ235739': '0.0103%', 'ТОВ228114 | ТОВ248429 | ТОВ184253 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ248429 | ТОВ139528': '0.0154%', 'ТОВ228114 | ТОВ248429 | ТОВ262977': '0.0133%', 'ТОВ228114 | ТОВ248429 | ТОВ232715': '0.0195%', 'ТОВ228114 | ТОВ248429 | ТОВ042704': '0.0113%', 'ТОВ228114 | ТОВ248429 | ТОВ231690': '0.0103%', 'ТОВ228114 | ТОВ248429 | ТОВ042547': '0.0195%', 'ТОВ228114 | ТОВ248429 | ТОВ235739': '0.0144%', 'ТОВ228114 | ТОВ248429 | ТОВ099797': '0.0103%', 'ТОВ228114 | ТОВ248429 | ТОВ227715': '0.0174%', 'ТОВ228114 | ТОВ248429 | ТОВ255036': '0.0154%', 'ТОВ228114 | ТОВ248429 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ248429 | ТОВ043107': '0.0113%', 'ТОВ228114 | ТОВ248429 | ТОВ032043': '0.0123%', 'ТОВ228114 | ТОВ231592 | ТОВ184253': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ045656': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ263281': '0.0349%', 'ТОВ228114 | ТОВ184253 | ТОВ263281 | ТОВ235739': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ263281 | ТОВ227717': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ139528': '0.0984%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ262977': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ232715': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ042704': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ042547': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ235739': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ227715': '0.0287%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ258133': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ255036': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ227717': '0.0236%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ037482': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ139528 | ТОВ032043': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ219818': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ235043': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ029182': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ232298': '0.0226%', 'ТОВ228114 | ТОВ184253 | ТОВ262977': '0.0584%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ232715': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ284483': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ042547': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ235739': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ301624': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ155841': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ227717': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ043107': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ262977 | ТОВ032043': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ232715': '0.0646%', 'ТОВ228114 | ТОВ184253 | ТОВ232715 | ТОВ042547': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ232715 | ТОВ235739': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ232715 | ТОВ227715': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ232715 | ТОВ255036': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ232715 | ТОВ227717': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ232715 | ТОВ032043': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ042372': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ027485': '0.0215%', 'ТОВ228114 | ТОВ184253 | ТОВ230418': '0.0318%', 'ТОВ228114 | ТОВ184253 | ТОВ193716': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ053041': '0.0287%', 'ТОВ228114 | ТОВ184253 | ТОВ231691': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ042704': '0.0256%', 'ТОВ228114 | ТОВ184253 | ТОВ093543': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ242124': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ186166': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ275802': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ234062': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ257894': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ239614': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ231690': '0.0236%', 'ТОВ228114 | ТОВ184253 | ТОВ236590': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ283493': '0.0267%', 'ТОВ228114 | ТОВ184253 | ТОВ223460': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ013612': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ213378': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ251102': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ165736': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ292698': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ090902': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ218365': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ284483': '0.0246%', 'ТОВ228114 | ТОВ184253 | ТОВ223175': '0.0226%', 'ТОВ228114 | ТОВ184253 | ТОВ042547': '0.0492%', 'ТОВ228114 | ТОВ184253 | ТОВ042547 | ТОВ235739': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ042547 | ТОВ227715': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ042547 | ТОВ301624': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ042547 | ТОВ155841': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ042547 | ТОВ255036': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ042547 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ204237': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ237987': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ214882': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ043791': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ224175': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ235739': '0.0769%', 'ТОВ228114 | ТОВ184253 | ТОВ235739 | ТОВ227715': '0.0256%', 'ТОВ228114 | ТОВ184253 | ТОВ235739 | ТОВ301624': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ235739 | ТОВ255036': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ235739 | ТОВ227717': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ235739 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ222081': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ227714': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ137898': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ170478': '0.0318%', 'ТОВ228114 | ТОВ184253 | ТОВ031116': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ227715': '0.0912%', 'ТОВ228114 | ТОВ184253 | ТОВ227715 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ227715 | ТОВ227717': '0.0267%', 'ТОВ228114 | ТОВ184253 | ТОВ227715 | ТОВ097249': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ227715 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ227715 | ТОВ249929': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ118223': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ268969': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ101971': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ264127': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ290898': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ252596': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ301624': '0.0451%', 'ТОВ228114 | ТОВ184253 | ТОВ301624 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ283303': '0.0226%', 'ТОВ228114 | ТОВ184253 | ТОВ217019': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ230700': '0.0287%', 'ТОВ228114 | ТОВ184253 | ТОВ143636': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ283145': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ256936': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ029305': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ155841': '0.0441%', 'ТОВ228114 | ТОВ184253 | ТОВ155841 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ155841 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ230168': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ258449': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ150733': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ042940': '0.0215%', 'ТОВ228114 | ТОВ184253 | ТОВ205039': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ138742': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ230122': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ237349': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ237348': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ141628': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ275655': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ264209': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ258133': '0.0226%', 'ТОВ228114 | ТОВ184253 | ТОВ030822': '0.0154%', 'ТОВ228114 | ТОВ184253 | ТОВ223173': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ178947': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ255036': '0.0584%', 'ТОВ228114 | ТОВ184253 | ТОВ255036 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ255036 | ТОВ032043': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ030046': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ200752': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ231680': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ130944': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ252669': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ227717': '0.0759%', 'ТОВ228114 | ТОВ184253 | ТОВ227717 | ТОВ032043': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ103847': '0.0226%', 'ТОВ228114 | ТОВ184253 | ТОВ108841': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ211323': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ043107': '0.0297%', 'ТОВ228114 | ТОВ184253 | ТОВ282911': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ268318': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ030718': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ247989': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ240397': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ037482': '0.0256%', 'ТОВ228114 | ТОВ184253 | ТОВ234712': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ097251': '0.0174%', 'ТОВ228114 | ТОВ184253 | ТОВ052777': '0.0318%', 'ТОВ228114 | ТОВ184253 | ТОВ042657': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ251198': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ296234': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ264386': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ232962': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ098311': '0.0246%', 'ТОВ228114 | ТОВ184253 | ТОВ156464': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ052792': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ237675': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ237378': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ171231': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ108033': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ255329': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ272060': '0.0144%', 'ТОВ228114 | ТОВ184253 | ТОВ044515': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ176886': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ177803': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ171225': '0.0185%', 'ТОВ228114 | ТОВ184253 | ТОВ097249': '0.0328%', 'ТОВ228114 | ТОВ184253 | ТОВ231439': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ128684': '0.0205%', 'ТОВ228114 | ТОВ184253 | ТОВ255285': '0.0113%', 'ТОВ228114 | ТОВ184253 | ТОВ177625': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ032043': '0.0605%', 'ТОВ228114 | ТОВ184253 | ТОВ280586': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ177642': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ275778': '0.0205%', 'ТОВ228114 | ТОВ184253 | ТОВ042839': '0.0123%', 'ТОВ228114 | ТОВ184253 | ТОВ249929': '0.0205%', 'ТОВ228114 | ТОВ184253 | ТОВ099791': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ244523': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ287107': '0.0133%', 'ТОВ228114 | ТОВ184253 | ТОВ256239': '0.0164%', 'ТОВ228114 | ТОВ184253 | ТОВ298801': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ278015': '0.0226%', 'ТОВ228114 | ТОВ184253 | ТОВ255197': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ129157': '0.0379%', 'ТОВ228114 | ТОВ184253 | ТОВ293477': '0.0195%', 'ТОВ228114 | ТОВ184253 | ТОВ231952': '0.0103%', 'ТОВ228114 | ТОВ184253 | ТОВ204058': '0.0113%', 'ТОВ228114 | ТОВ263281 | ТОВ232715': '0.0123%', 'ТОВ228114 | ТОВ263281 | ТОВ235739': '0.0195%', 'ТОВ228114 | ТОВ263281 | ТОВ227715': '0.0144%', 'ТОВ228114 | ТОВ263281 | ТОВ227717': '0.0164%', 'ТОВ228114 | ТОВ139528 | ТОВ232298': '0.0164%', 'ТОВ228114 | ТОВ139528 | ТОВ262977': '0.0287%', 'ТОВ228114 | ТОВ139528 | ТОВ232715': '0.0349%', 'ТОВ228114 | ТОВ139528 | ТОВ232715 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ230418': '0.0215%', 'ТОВ228114 | ТОВ139528 | ТОВ193716': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ231691': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ042704': '0.0144%', 'ТОВ228114 | ТОВ139528 | ТОВ239614': '0.0133%', 'ТОВ228114 | ТОВ139528 | ТОВ231690': '0.0144%', 'ТОВ228114 | ТОВ139528 | ТОВ165736': '0.0133%', 'ТОВ228114 | ТОВ139528 | ТОВ090902': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ284483': '0.0133%', 'ТОВ228114 | ТОВ139528 | ТОВ042547': '0.0338%', 'ТОВ228114 | ТОВ139528 | ТОВ042547 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ042547 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ235739': '0.0287%', 'ТОВ228114 | ТОВ139528 | ТОВ235739 | ТОВ227715': '0.0113%', 'ТОВ228114 | ТОВ139528 | ТОВ099797': '0.0297%', 'ТОВ228114 | ТОВ139528 | ТОВ137898': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ170478': '0.0113%', 'ТОВ228114 | ТОВ139528 | ТОВ227715': '0.0543%', 'ТОВ228114 | ТОВ139528 | ТОВ227715 | ТОВ227717': '0.0185%', 'ТОВ228114 | ТОВ139528 | ТОВ301624': '0.0164%', 'ТОВ228114 | ТОВ139528 | ТОВ283303': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ230700': '0.0205%', 'ТОВ228114 | ТОВ139528 | ТОВ230168': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ138742': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ237348': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ258133': '0.0133%', 'ТОВ228114 | ТОВ139528 | ТОВ178947': '0.0113%', 'ТОВ228114 | ТОВ139528 | ТОВ255036': '0.0318%', 'ТОВ228114 | ТОВ139528 | ТОВ227717': '0.0431%', 'ТОВ228114 | ТОВ139528 | ТОВ043107': '0.0164%', 'ТОВ228114 | ТОВ139528 | ТОВ247989': '0.0164%', 'ТОВ228114 | ТОВ139528 | ТОВ037482': '0.0133%', 'ТОВ228114 | ТОВ139528 | ТОВ098311': '0.0113%', 'ТОВ228114 | ТОВ139528 | ТОВ237675': '0.0113%', 'ТОВ228114 | ТОВ139528 | ТОВ171225': '0.0103%', 'ТОВ228114 | ТОВ139528 | ТОВ097249': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ128684': '0.0144%', 'ТОВ228114 | ТОВ139528 | ТОВ032043': '0.0236%', 'ТОВ228114 | ТОВ139528 | ТОВ249929': '0.0123%', 'ТОВ228114 | ТОВ139528 | ТОВ099791': '0.0133%', 'ТОВ228114 | ТОВ029182 | ТОВ262977': '0.0154%', 'ТОВ228114 | ТОВ029182 | ТОВ232715': '0.0123%', 'ТОВ228114 | ТОВ029182 | ТОВ042547': '0.0103%', 'ТОВ228114 | ТОВ029182 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ029182 | ТОВ043107': '0.0185%', 'ТОВ228114 | ТОВ232298 | ТОВ262977': '0.0133%', 'ТОВ228114 | ТОВ232298 | ТОВ232715': '0.0205%', 'ТОВ228114 | ТОВ232298 | ТОВ232297': '0.0185%', 'ТОВ228114 | ТОВ232298 | ТОВ042704': '0.0113%', 'ТОВ228114 | ТОВ232298 | ТОВ235739': '0.0133%', 'ТОВ228114 | ТОВ232298 | ТОВ227715': '0.0195%', 'ТОВ228114 | ТОВ232298 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ232298 | ТОВ227717': '0.0236%', 'ТОВ228114 | ТОВ262977 | ТОВ232715': '0.0308%', 'ТОВ228114 | ТОВ262977 | ТОВ232715 | ТОВ227715': '0.0113%', 'ТОВ228114 | ТОВ262977 | ТОВ232715 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ230418': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ231691': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ042704': '0.0113%', 'ТОВ228114 | ТОВ262977 | ТОВ242124': '0.0113%', 'ТОВ228114 | ТОВ262977 | ТОВ283493': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ223460': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ045822': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ284483': '0.0164%', 'ТОВ228114 | ТОВ262977 | ТОВ223175': '0.0144%', 'ТОВ228114 | ТОВ262977 | ТОВ042547': '0.0267%', 'ТОВ228114 | ТОВ262977 | ТОВ042547 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ204237': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ224175': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ235739': '0.0205%', 'ТОВ228114 | ТОВ262977 | ТОВ235739 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ227714': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ099797': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ137898': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ227715': '0.0308%', 'ТОВ228114 | ТОВ262977 | ТОВ227715 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ262977 | ТОВ101971': '0.0113%', 'ТОВ228114 | ТОВ262977 | ТОВ301624': '0.0226%', 'ТОВ228114 | ТОВ262977 | ТОВ230700': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ155841': '0.0215%', 'ТОВ228114 | ТОВ262977 | ТОВ138742': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ030822': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ178947': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ255036': '0.0359%', 'ТОВ228114 | ТОВ262977 | ТОВ255036 | ТОВ043107': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ227717': '0.0308%', 'ТОВ228114 | ТОВ262977 | ТОВ108841': '0.0205%', 'ТОВ228114 | ТОВ262977 | ТОВ043107': '0.0369%', 'ТОВ228114 | ТОВ262977 | ТОВ282911': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ247989': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ037482': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ052777': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ264386': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ232962': '0.0133%', 'ТОВ228114 | ТОВ262977 | ТОВ177803': '0.0113%', 'ТОВ228114 | ТОВ262977 | ТОВ097249': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ177625': '0.0154%', 'ТОВ228114 | ТОВ262977 | ТОВ032043': '0.0246%', 'ТОВ228114 | ТОВ262977 | ТОВ249929': '0.0103%', 'ТОВ228114 | ТОВ262977 | ТОВ278015': '0.0123%', 'ТОВ228114 | ТОВ262977 | ТОВ129157': '0.0123%', 'ТОВ228114 | ТОВ232715 | ТОВ232297': '0.0113%', 'ТОВ228114 | ТОВ232715 | ТОВ042704': '0.0174%', 'ТОВ228114 | ТОВ232715 | ТОВ231690': '0.0144%', 'ТОВ228114 | ТОВ232715 | ТОВ283493': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ223460': '0.0174%', 'ТОВ228114 | ТОВ232715 | ТОВ284483': '0.0133%', 'ТОВ228114 | ТОВ232715 | ТОВ042547': '0.0256%', 'ТОВ228114 | ТОВ232715 | ТОВ042547 | ТОВ227715': '0.0113%', 'ТОВ228114 | ТОВ232715 | ТОВ042547 | ТОВ255036': '0.0144%', 'ТОВ228114 | ТОВ232715 | ТОВ204237': '0.0133%', 'ТОВ228114 | ТОВ232715 | ТОВ224175': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ235739': '0.0267%', 'ТОВ228114 | ТОВ232715 | ТОВ099797': '0.0133%', 'ТОВ228114 | ТОВ232715 | ТОВ227715': '0.0420%', 'ТОВ228114 | ТОВ232715 | ТОВ227715 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ232715 | ТОВ252596': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ301624': '0.0154%', 'ТОВ228114 | ТОВ232715 | ТОВ283303': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ217019': '0.0113%', 'ТОВ228114 | ТОВ232715 | ТОВ230700': '0.0164%', 'ТОВ228114 | ТОВ232715 | ТОВ155841': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ138742': '0.0123%', 'ТОВ228114 | ТОВ232715 | ТОВ237348': '0.0113%', 'ТОВ228114 | ТОВ232715 | ТОВ178947': '0.0133%', 'ТОВ228114 | ТОВ232715 | ТОВ255036': '0.0359%', 'ТОВ228114 | ТОВ232715 | ТОВ030046': '0.0123%', 'ТОВ228114 | ТОВ232715 | ТОВ227717': '0.0287%', 'ТОВ228114 | ТОВ232715 | ТОВ103847': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ043107': '0.0195%', 'ТОВ228114 | ТОВ232715 | ТОВ282911': '0.0123%', 'ТОВ228114 | ТОВ232715 | ТОВ037482': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ052777': '0.0113%', 'ТОВ228114 | ТОВ232715 | ТОВ098311': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ097249': '0.0144%', 'ТОВ228114 | ТОВ232715 | ТОВ032043': '0.0215%', 'ТОВ228114 | ТОВ232715 | ТОВ269567': '0.0103%', 'ТОВ228114 | ТОВ232715 | ТОВ249929': '0.0133%', 'ТОВ228114 | ТОВ232715 | ТОВ129157': '0.0113%', 'ТОВ228114 | ТОВ027485 | ТОВ227715': '0.0113%', 'ТОВ228114 | ТОВ230418 | ТОВ053041': '0.0103%', 'ТОВ228114 | ТОВ230418 | ТОВ235739': '0.0113%', 'ТОВ228114 | ТОВ230418 | ТОВ227715': '0.0154%', 'ТОВ228114 | ТОВ230418 | ТОВ301624': '0.0133%', 'ТОВ228114 | ТОВ230418 | ТОВ230700': '0.0113%', 'ТОВ228114 | ТОВ230418 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ230418 | ТОВ227717': '0.0144%', 'ТОВ228114 | ТОВ230418 | ТОВ032043': '0.0174%', 'ТОВ228114 | ТОВ193716 | ТОВ230700': '0.0144%', 'ТОВ228114 | ТОВ193716 | ТОВ227717': '0.0164%', 'ТОВ228114 | ТОВ232297 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ232297 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ053041 | ТОВ227715': '0.0154%', 'ТОВ228114 | ТОВ053041 | ТОВ230700': '0.0113%', 'ТОВ228114 | ТОВ053041 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ042704 | ТОВ042547': '0.0144%', 'ТОВ228114 | ТОВ042704 | ТОВ235739': '0.0174%', 'ТОВ228114 | ТОВ042704 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ042704 | ТОВ155841': '0.0103%', 'ТОВ228114 | ТОВ042704 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ042704 | ТОВ227717': '0.0195%', 'ТОВ228114 | ТОВ042704 | ТОВ097249': '0.0113%', 'ТОВ228114 | ТОВ231690 | ТОВ235739': '0.0123%', 'ТОВ228114 | ТОВ231690 | ТОВ227715': '0.0174%', 'ТОВ228114 | ТОВ231690 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ231690 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ231690 | ТОВ043107': '0.0103%', 'ТОВ228114 | ТОВ283493 | ТОВ227715': '0.0113%', 'ТОВ228114 | ТОВ283493 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ223460 | ТОВ227715': '0.0164%', 'ТОВ228114 | ТОВ223460 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ223460 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ090902 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ218365 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ284483 | ТОВ042547': '0.0103%', 'ТОВ228114 | ТОВ284483 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ284483 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ284483 | ТОВ227717': '0.0123%', 'ТОВ228114 | ТОВ223175 | ТОВ042547': '0.0144%', 'ТОВ228114 | ТОВ223175 | ТОВ235739': '0.0144%', 'ТОВ228114 | ТОВ223175 | ТОВ099797': '0.0103%', 'ТОВ228114 | ТОВ223175 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ223175 | ТОВ255036': '0.0195%', 'ТОВ228114 | ТОВ223175 | ТОВ227717': '0.0154%', 'ТОВ228114 | ТОВ042547 | ТОВ235739': '0.0246%', 'ТОВ228114 | ТОВ042547 | ТОВ235739 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ042547 | ТОВ235739 | ТОВ255036': '0.0113%', 'ТОВ228114 | ТОВ042547 | ТОВ099797': '0.0164%', 'ТОВ228114 | ТОВ042547 | ТОВ227715': '0.0297%', 'ТОВ228114 | ТОВ042547 | ТОВ227715 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ042547 | ТОВ227715 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ042547 | ТОВ301624': '0.0174%', 'ТОВ228114 | ТОВ042547 | ТОВ029305': '0.0144%', 'ТОВ228114 | ТОВ042547 | ТОВ155841': '0.0144%', 'ТОВ228114 | ТОВ042547 | ТОВ178947': '0.0133%', 'ТОВ228114 | ТОВ042547 | ТОВ255036': '0.0410%', 'ТОВ228114 | ТОВ042547 | ТОВ227717': '0.0277%', 'ТОВ228114 | ТОВ042547 | ТОВ043107': '0.0154%', 'ТОВ228114 | ТОВ042547 | ТОВ247989': '0.0103%', 'ТОВ228114 | ТОВ042547 | ТОВ232962': '0.0113%', 'ТОВ228114 | ТОВ042547 | ТОВ097249': '0.0123%', 'ТОВ228114 | ТОВ042547 | ТОВ128684': '0.0123%', 'ТОВ228114 | ТОВ042547 | ТОВ032043': '0.0164%', 'ТОВ228114 | ТОВ204237 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ214882 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ235739 | ТОВ227714': '0.0133%', 'ТОВ228114 | ТОВ235739 | ТОВ099797': '0.0144%', 'ТОВ228114 | ТОВ235739 | ТОВ170478': '0.0154%', 'ТОВ228114 | ТОВ235739 | ТОВ227715': '0.0390%', 'ТОВ228114 | ТОВ235739 | ТОВ227715 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ235739 | ТОВ227715 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ235739 | ТОВ301624': '0.0287%', 'ТОВ228114 | ТОВ235739 | ТОВ217019': '0.0103%', 'ТОВ228114 | ТОВ235739 | ТОВ155841': '0.0123%', 'ТОВ228114 | ТОВ235739 | ТОВ255036': '0.0287%', 'ТОВ228114 | ТОВ235739 | ТОВ227717': '0.0328%', 'ТОВ228114 | ТОВ235739 | ТОВ043107': '0.0133%', 'ТОВ228114 | ТОВ235739 | ТОВ037482': '0.0123%', 'ТОВ228114 | ТОВ235739 | ТОВ052777': '0.0103%', 'ТОВ228114 | ТОВ235739 | ТОВ098311': '0.0103%', 'ТОВ228114 | ТОВ235739 | ТОВ032043': '0.0195%', 'ТОВ228114 | ТОВ235739 | ТОВ249929': '0.0113%', 'ТОВ228114 | ТОВ235739 | ТОВ129157': '0.0133%', 'ТОВ228114 | ТОВ227714 | ТОВ227715': '0.0113%', 'ТОВ228114 | ТОВ227714 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ227714 | ТОВ227717': '0.0123%', 'ТОВ228114 | ТОВ227714 | ТОВ227716': '0.0113%', 'ТОВ228114 | ТОВ099797 | ТОВ227715': '0.0226%', 'ТОВ228114 | ТОВ099797 | ТОВ230700': '0.0103%', 'ТОВ228114 | ТОВ099797 | ТОВ178947': '0.0113%', 'ТОВ228114 | ТОВ099797 | ТОВ255036': '0.0154%', 'ТОВ228114 | ТОВ099797 | ТОВ227717': '0.0185%', 'ТОВ228114 | ТОВ099797 | ТОВ043107': '0.0123%', 'ТОВ228114 | ТОВ099797 | ТОВ097249': '0.0103%', 'ТОВ228114 | ТОВ099797 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ099797 | ТОВ177642': '0.0133%', 'ТОВ228114 | ТОВ137898 | ТОВ227715': '0.0103%', 'ТОВ228114 | ТОВ137898 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ137898 | ТОВ247989': '0.0103%', 'ТОВ228114 | ТОВ170478 | ТОВ227715': '0.0123%', 'ТОВ228114 | ТОВ170478 | ТОВ230700': '0.0123%', 'ТОВ228114 | ТОВ170478 | ТОВ155841': '0.0133%', 'ТОВ228114 | ТОВ170478 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ301624': '0.0185%', 'ТОВ228114 | ТОВ227715 | ТОВ230700': '0.0277%', 'ТОВ228114 | ТОВ227715 | ТОВ249439': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ155841': '0.0154%', 'ТОВ228114 | ТОВ227715 | ТОВ230168': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ150733': '0.0113%', 'ТОВ228114 | ТОВ227715 | ТОВ042940': '0.0113%', 'ТОВ228114 | ТОВ227715 | ТОВ230122': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ258133': '0.0123%', 'ТОВ228114 | ТОВ227715 | ТОВ178947': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ255036': '0.0390%', 'ТОВ228114 | ТОВ227715 | ТОВ231680': '0.0123%', 'ТОВ228114 | ТОВ227715 | ТОВ227717': '0.0574%', 'ТОВ228114 | ТОВ227715 | ТОВ103847': '0.0174%', 'ТОВ228114 | ТОВ227715 | ТОВ043107': '0.0133%', 'ТОВ228114 | ТОВ227715 | ТОВ247989': '0.0144%', 'ТОВ228114 | ТОВ227715 | ТОВ037482': '0.0144%', 'ТОВ228114 | ТОВ227715 | ТОВ052777': '0.0144%', 'ТОВ228114 | ТОВ227715 | ТОВ264386': '0.0123%', 'ТОВ228114 | ТОВ227715 | ТОВ098311': '0.0113%', 'ТОВ228114 | ТОВ227715 | ТОВ097249': '0.0215%', 'ТОВ228114 | ТОВ227715 | ТОВ128684': '0.0113%', 'ТОВ228114 | ТОВ227715 | ТОВ032043': '0.0174%', 'ТОВ228114 | ТОВ227715 | ТОВ177642': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ275778': '0.0113%', 'ТОВ228114 | ТОВ227715 | ТОВ249929': '0.0205%', 'ТОВ228114 | ТОВ227715 | ТОВ099791': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ287107': '0.0113%', 'ТОВ228114 | ТОВ227715 | ТОВ162247': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ278015': '0.0133%', 'ТОВ228114 | ТОВ227715 | ТОВ255197': '0.0103%', 'ТОВ228114 | ТОВ227715 | ТОВ129157': '0.0144%', 'ТОВ228114 | ТОВ252596 | ТОВ227717': '0.0103%', 'ТОВ228114 | ТОВ301624 | ТОВ029305': '0.0103%', 'ТОВ228114 | ТОВ301624 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ301624 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ301624 | ТОВ043107': '0.0103%', 'ТОВ228114 | ТОВ301624 | ТОВ037482': '0.0133%', 'ТОВ228114 | ТОВ301624 | ТОВ032043': '0.0174%', 'ТОВ228114 | ТОВ301624 | ТОВ129157': '0.0103%', 'ТОВ228114 | ТОВ283303 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ217019 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ217019 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ230700 | ТОВ255036': '0.0154%', 'ТОВ228114 | ТОВ230700 | ТОВ227717': '0.0154%', 'ТОВ228114 | ТОВ029305 | ТОВ255036': '0.0133%', 'ТОВ228114 | ТОВ249439 | ТОВ255036': '0.0144%', 'ТОВ228114 | ТОВ155841 | ТОВ255036': '0.0174%', 'ТОВ228114 | ТОВ155841 | ТОВ043107': '0.0123%', 'ТОВ228114 | ТОВ155841 | ТОВ098311': '0.0103%', 'ТОВ228114 | ТОВ155841 | ТОВ097249': '0.0123%', 'ТОВ228114 | ТОВ155841 | ТОВ032043': '0.0144%', 'ТОВ228114 | ТОВ042940 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ042940 | ТОВ227717': '0.0103%', 'ТОВ228114 | ТОВ237348 | ТОВ227717': '0.0113%', 'ТОВ228114 | ТОВ258133 | ТОВ227717': '0.0133%', 'ТОВ228114 | ТОВ030822 | ТОВ255036': '0.0103%', 'ТОВ228114 | ТОВ030822 | ТОВ043107': '0.0103%', 'ТОВ228114 | ТОВ178947 | ТОВ255036': '0.0123%', 'ТОВ228114 | ТОВ178947 | ТОВ032043': '0.0103%', 'ТОВ228114 | ТОВ255036 | ТОВ227717': '0.0267%', 'ТОВ228114 | ТОВ255036 | ТОВ103847': '0.0113%', 'ТОВ228114 | ТОВ255036 | ТОВ043107': '0.0236%', 'ТОВ228114 | ТОВ255036 | ТОВ247989': '0.0154%', 'ТОВ228114 | ТОВ255036 | ТОВ037482': '0.0133%', 'ТОВ228114 | ТОВ255036 | ТОВ097251': '0.0103%', 'ТОВ228114 | ТОВ255036 | ТОВ052777': '0.0144%', 'ТОВ228114 | ТОВ255036 | ТОВ264386': '0.0123%', 'ТОВ228114 | ТОВ255036 | ТОВ232962': '0.0103%', 'ТОВ228114 | ТОВ255036 | ТОВ177803': '0.0103%', 'ТОВ228114 | ТОВ255036 | ТОВ097249': '0.0123%', 'ТОВ228114 | ТОВ255036 | ТОВ128684': '0.0133%', 'ТОВ228114 | ТОВ255036 | ТОВ032043': '0.0256%', 'ТОВ228114 | ТОВ255036 | ТОВ278015': '0.0113%', 'ТОВ228114 | ТОВ255036 | ТОВ129157': '0.0133%', 'ТОВ228114 | ТОВ227717 | ТОВ108841': '0.0144%', 'ТОВ228114 | ТОВ227717 | ТОВ043107': '0.0154%', 'ТОВ228114 | ТОВ227717 | ТОВ247989': '0.0103%', 'ТОВ228114 | ТОВ227717 | ТОВ037482': '0.0144%', 'ТОВ228114 | ТОВ227717 | ТОВ097251': '0.0123%', 'ТОВ228114 | ТОВ227717 | ТОВ052777': '0.0103%', 'ТОВ228114 | ТОВ227717 | ТОВ153780': '0.0103%', 'ТОВ228114 | ТОВ227717 | ТОВ264386': '0.0103%', 'ТОВ228114 | ТОВ227717 | ТОВ232962': '0.0144%', 'ТОВ228114 | ТОВ227717 | ТОВ237675': '0.0174%', 'ТОВ228114 | ТОВ227717 | ТОВ177803': '0.0113%', 'ТОВ228114 | ТОВ227717 | ТОВ097249': '0.0174%', 'ТОВ228114 | ТОВ227717 | ТОВ032043': '0.0256%', 'ТОВ228114 | ТОВ227717 | ТОВ249929': '0.0164%', 'ТОВ228114 | ТОВ227717 | ТОВ129157': '0.0133%', 'ТОВ228114 | ТОВ108841 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ043107 | ТОВ052792': '0.0113%', 'ТОВ228114 | ТОВ043107 | ТОВ097249': '0.0133%', 'ТОВ228114 | ТОВ043107 | ТОВ177625': '0.0123%', 'ТОВ228114 | ТОВ043107 | ТОВ032043': '0.0123%', 'ТОВ228114 | ТОВ037482 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ037482 | ТОВ129157': '0.0103%', 'ТОВ228114 | ТОВ097251 | ТОВ097249': '0.0133%', 'ТОВ228114 | ТОВ097251 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ232962 | ТОВ032043': '0.0113%', 'ТОВ228114 | ТОВ097249 | ТОВ032043': '0.0174%', 'ТОВ228114 | ТОВ032043 | ТОВ129157': '0.0154%', 'ТОВ228114 | ТОВ171218 | ТОВ171243': '0.0103%', 'ТОВ279361 | ТОВ231586 | ТОВ219150': '0.0133%', 'ТОВ279361 | ТОВ231586 | ТОВ109423': '0.0144%', 'ТОВ279361 | ТОВ231586 | ТОВ206304': '0.0154%', 'ТОВ279361 | ТОВ231586 | ТОВ231590': '0.0369%', 'ТОВ279361 | ТОВ231586 | ТОВ231590 | ТОВ184253': '0.0144%', 'ТОВ279361 | ТОВ231586 | ТОВ284416': '0.0123%', 'ТОВ279361 | ТОВ231586 | ТОВ106930': '0.0205%', 'ТОВ279361 | ТОВ231586 | ТОВ259350': '0.0133%', 'ТОВ279361 | ТОВ231586 | ТОВ166306': '0.0174%', 'ТОВ279361 | ТОВ231586 | ТОВ130818': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ224035': '0.0144%', 'ТОВ279361 | ТОВ231586 | ТОВ248429': '0.0103%', 'ТОВ279361 | ТОВ231586 | ТОВ184253': '0.0533%', 'ТОВ279361 | ТОВ231586 | ТОВ184253 | ТОВ139528': '0.0164%', 'ТОВ279361 | ТОВ231586 | ТОВ184253 | ТОВ262977': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ184253 | ТОВ232715': '0.0195%', 'ТОВ279361 | ТОВ231586 | ТОВ184253 | ТОВ227714': '0.0103%', 'ТОВ279361 | ТОВ231586 | ТОВ263281': '0.0123%', 'ТОВ279361 | ТОВ231586 | ТОВ139528': '0.0297%', 'ТОВ279361 | ТОВ231586 | ТОВ139528 | ТОВ232715': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ262977': '0.0205%', 'ТОВ279361 | ТОВ231586 | ТОВ232715': '0.0554%', 'ТОВ279361 | ТОВ231586 | ТОВ232715 | ТОВ053041': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ279046': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ230418': '0.0133%', 'ТОВ279361 | ТОВ231586 | ТОВ053041': '0.0195%', 'ТОВ279361 | ТОВ231586 | ТОВ231691': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ042704': '0.0164%', 'ТОВ279361 | ТОВ231586 | ТОВ231690': '0.0133%', 'ТОВ279361 | ТОВ231586 | ТОВ236590': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ283493': '0.0246%', 'ТОВ279361 | ТОВ231586 | ТОВ223460': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ165736': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ042547': '0.0205%', 'ТОВ279361 | ТОВ231586 | ТОВ224175': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ222081': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ227714': '0.0267%', 'ТОВ279361 | ТОВ231586 | ТОВ227715': '0.0123%', 'ТОВ279361 | ТОВ231586 | ТОВ118223': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ101971': '0.0103%', 'ТОВ279361 | ТОВ231586 | ТОВ283303': '0.0154%', 'ТОВ279361 | ТОВ231586 | ТОВ230700': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ155841': '0.0103%', 'ТОВ279361 | ТОВ231586 | ТОВ230168': '0.0123%', 'ТОВ279361 | ТОВ231586 | ТОВ042940': '0.0133%', 'ТОВ279361 | ТОВ231586 | ТОВ237349': '0.0123%', 'ТОВ279361 | ТОВ231586 | ТОВ178947': '0.0174%', 'ТОВ279361 | ТОВ231586 | ТОВ255036': '0.0226%', 'ТОВ279361 | ТОВ231586 | ТОВ227717': '0.0103%', 'ТОВ279361 | ТОВ231586 | ТОВ043107': '0.0185%', 'ТОВ279361 | ТОВ231586 | ТОВ282911': '0.0205%', 'ТОВ279361 | ТОВ231586 | ТОВ247989': '0.0195%', 'ТОВ279361 | ТОВ231586 | ТОВ232962': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ000643': '0.0113%', 'ТОВ279361 | ТОВ231586 | ТОВ032043': '0.0123%', 'ТОВ279361 | ТОВ231586 | ТОВ287107': '0.0103%', 'ТОВ279361 | ТОВ219150 | ТОВ245168': '0.0113%', 'ТОВ279361 | ТОВ219150 | ТОВ166306': '0.0103%', 'ТОВ279361 | ТОВ109423 | ТОВ166306': '0.0103%', 'ТОВ279361 | ТОВ109423 | ТОВ184253': '0.0236%', 'ТОВ279361 | ТОВ109423 | ТОВ139528': '0.0154%', 'ТОВ279361 | ТОВ109423 | ТОВ232715': '0.0174%', 'ТОВ279361 | ТОВ109423 | ТОВ053041': '0.0144%', 'ТОВ279361 | ТОВ109423 | ТОВ283493': '0.0103%', 'ТОВ279361 | ТОВ109423 | ТОВ042547': '0.0144%', 'ТОВ279361 | ТОВ109423 | ТОВ227714': '0.0205%', 'ТОВ279361 | ТОВ109423 | ТОВ227714 | ТОВ227716': '0.0133%', 'ТОВ279361 | ТОВ109423 | ТОВ227715': '0.0144%', 'ТОВ279361 | ТОВ109423 | ТОВ301624': '0.0103%', 'ТОВ279361 | ТОВ109423 | ТОВ258133': '0.0123%', 'ТОВ279361 | ТОВ109423 | ТОВ255036': '0.0164%', 'ТОВ279361 | ТОВ109423 | ТОВ227717': '0.0133%', 'ТОВ279361 | ТОВ109423 | ТОВ227716': '0.0144%', 'ТОВ279361 | ТОВ109423 | ТОВ032043': '0.0123%', 'ТОВ279361 | ТОВ033048 | ТОВ184253': '0.0267%', 'ТОВ279361 | ТОВ033048 | ТОВ139528': '0.0144%', 'ТОВ279361 | ТОВ033048 | ТОВ262977': '0.0154%', 'ТОВ279361 | ТОВ033048 | ТОВ232715': '0.0123%', 'ТОВ279361 | ТОВ033048 | ТОВ283493': '0.0113%', 'ТОВ279361 | ТОВ033048 | ТОВ227714': '0.0174%', 'ТОВ279361 | ТОВ033048 | ТОВ227714 | ТОВ227716': '0.0103%', 'ТОВ279361 | ТОВ033048 | ТОВ255036': '0.0154%', 'ТОВ279361 | ТОВ033048 | ТОВ227717': '0.0123%', 'ТОВ279361 | ТОВ033048 | ТОВ227716': '0.0123%', 'ТОВ279361 | ТОВ033048 | ТОВ043107': '0.0113%', 'ТОВ279361 | ТОВ033048 | ТОВ032043': '0.0133%', 'ТОВ279361 | ТОВ033048 | ТОВ129157': '0.0103%', 'ТОВ279361 | ТОВ206304 | ТОВ184253': '0.0174%', 'ТОВ279361 | ТОВ206304 | ТОВ139528': '0.0113%', 'ТОВ279361 | ТОВ206304 | ТОВ232298': '0.0103%', 'ТОВ279361 | ТОВ206304 | ТОВ262977': '0.0123%', 'ТОВ279361 | ТОВ206304 | ТОВ232715': '0.0267%', 'ТОВ279361 | ТОВ206304 | ТОВ227714': '0.0113%', 'ТОВ279361 | ТОВ284497 | ТОВ232715': '0.0185%', 'ТОВ279361 | ТОВ001465 | ТОВ184253': '0.0144%', 'ТОВ279361 | ТОВ001465 | ТОВ232715': '0.0133%', 'ТОВ279361 | ТОВ001465 | ТОВ227714': '0.0103%', 'ТОВ279361 | ТОВ215649 | ТОВ106930': '0.0103%', 'ТОВ279361 | ТОВ215649 | ТОВ139528': '0.0113%', 'ТОВ279361 | ТОВ215649 | ТОВ232715': '0.0195%', 'ТОВ279361 | ТОВ277638 | ТОВ232715': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ106930': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ166306': '0.0123%', 'ТОВ279361 | ТОВ231590 | ТОВ184253': '0.0338%', 'ТОВ279361 | ТОВ231590 | ТОВ184253 | ТОВ139528': '0.0123%', 'ТОВ279361 | ТОВ231590 | ТОВ184253 | ТОВ232715': '0.0123%', 'ТОВ279361 | ТОВ231590 | ТОВ139528': '0.0195%', 'ТОВ279361 | ТОВ231590 | ТОВ232715': '0.0277%', 'ТОВ279361 | ТОВ231590 | ТОВ042704': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ283493': '0.0164%', 'ТОВ279361 | ТОВ231590 | ТОВ042547': '0.0133%', 'ТОВ279361 | ТОВ231590 | ТОВ235739': '0.0113%', 'ТОВ279361 | ТОВ231590 | ТОВ227714': '0.0195%', 'ТОВ279361 | ТОВ231590 | ТОВ227715': '0.0123%', 'ТОВ279361 | ТОВ231590 | ТОВ301624': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ283303': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ230168': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ178947': '0.0103%', 'ТОВ279361 | ТОВ231590 | ТОВ255036': '0.0164%', 'ТОВ279361 | ТОВ231590 | ТОВ227717': '0.0133%', 'ТОВ279361 | ТОВ231590 | ТОВ282911': '0.0113%', 'ТОВ279361 | ТОВ284416 | ТОВ259350': '0.0103%', 'ТОВ279361 | ТОВ284416 | ТОВ184253': '0.0226%', 'ТОВ279361 | ТОВ284416 | ТОВ232715': '0.0226%', 'ТОВ279361 | ТОВ224330 | ТОВ184253': '0.0123%', 'ТОВ279361 | ТОВ298806 | ТОВ232715': '0.0103%', 'ТОВ279361 | ТОВ120235 | ТОВ184253': '0.0123%', 'ТОВ279361 | ТОВ193295 | ТОВ184253': '0.0113%', ...}
На обычном компьютере решение этой задачки заняло по сути ночь. На cloud-платформах было бы быстрее:) Но, главное, клиент доволен.
Как видно, реализовать алгоритм своими силами довольно просто, хотя с эффективностью стоит поработать:)
И вновь пользователи R ликуют, для них никаких танцев с бубном делать не надо, все по аналогии с apriori.
Запускаем библиотеку и читаем данные:
$library(arules)$
Быстрый взгляд на датасет:
Правила:
И смотрим на результаты:
FP-Growth (Frequent Pattern Growth) алгоритм самый молодой из нашей троицы, впервые он описан в 2000 году в [7]. FP-Growth предлагает радикальную вещь - отказаться от генерации кандидатов (напомним, генерация кандидатов лежит в основе Apriori и ECLAT). Теоретчиески, такой подход позволит еще больше увеличить скорость алгоритма и использовать еще меньше памяти.
Это достигается за счет хранения в памяти префиксного дерева (trie) не из комбинаций кандидатов, а из самих транзакций. При этом FP-Growth генерирует таблицу заголовков для каждого item, чей $supp$ выше заданного пользователем. Эта таблица заголовков хранит связанный список всех однотипных узлов префиксного дерева. Таким образом, алгоритм сочетает в себе плюсы BFS за счет таблицы заголовков и DFS за счет построения trie. Псевдокод алгоритма схож с ECALT, за некоторыми исключениями.
ВХОД: Датасет $D$, содержащий список транзакций, $\sigma$ - задаваемый пользователем порог $supp$ и префикс $I \subseteq J$
ВЫХОД: Список itemsets $F[I](D, \sigma)$ для соответсвующего префикса $I$
ПОДХОД:
Реализации FP-Growth в Питоне повезло не больше, чем другим ALR-алгоритмам. Стандартных библиотек под него нет.
Неплохо FP_Growth представлен в pyspark, смотреть тут
Потестим второй вариант
#!pip install pyfpgrowth - установка
import pyfpgrowth
#Сгенериуем паттерны
patterns = pyfpgrowth.find_frequent_patterns(transactions, 2)
Wall time: 1min 38s
#Выучим правила
rules = pyfpgrowth.generate_association_rules(patterns, 30);
#Покажем
rules;
В данном случае R не отстает от Питона: в такой удобной и родной arules библиотеке FP-Growth отсутствует.
В то же время, как и для Питона, реализация сущетсвует в Spark - Ссылка
А на самом деле, если вам захочется применять ARL в ваших бизнес задачах, мы настоятельно рекомендуем учить Java.
Weka (Waikato Environment for Knowledge Analysis). Это бесплатное ПО для Машинного Обучения, написанное на языке Java. Разаботано в Университете Waikato в Новой Зеландии в 1993. В Weka есть как GUI, так и возможность работы из командной строки. Из преимуществ можно назвать простоту в использовании графического интерфейса - нет необходимости писать код для решения прикладных задач. Для использования библиотек Weka в Python можно установить оболочку для Weka в Python: python-weka-wrapper3. Оболочка исползует пакет javabridge для доступа к API Weka. Детальные инструкции по установке можно найти здесь.
SPMF Это библиотека для интеллектуального анализа данных с открытым исходным кодом, написанная на Java, специализирующаяся на поиске паттернов в данных (ссылка). Заявляется, что в SPMF реализовано более 55 алгоритмов для майнинга данных. К сожалению, официальной оболочки SPMF для Python нет (по крайней мере на дату написания данной статьи:) )
В заключении давайте эмпирически сравним эффективность метрикой runtime в зависимости от плотности датасета и длин транзакций датасета[9].
Под плотностью датасета подразумеваестя отношение транзакций, содержащих в себе частые items к общему количеству транзакций.
Из графика очевидно, что эффективность (чем меньше runtime, тем эффективнее) Apriori-алгоритма падает при увеличении плотности датасета.
Под длинной транзакции понимается количество в items в itemset
Очевидно, что при увеличении длины транзакции Apriori также справляется гораздо хуже.
Итак, мы познакомились с базовой теорией ARL ("кто купил х, также купил y") и основными понятиями и метриками (support, confidence, lift и conviction).
Посмотрели 3 самых популярных алгоритма (Apriori, ECLAT, FP-Growth), позавидовали пользователям R и библиотеки arules, попробовали сами реализовать ECALT.
Основные моменты:
Помимо рассмотренных бызовых алгоритмов существет модификации и ответвления:
Алгоритм CHARM для поиска *замкнутых* itemsets. Этот алгоритм отлично снижает сложность поиска правил с экспоненциальной (т.е. возрастающей при увеличении датасета, например) до полиномиальной. Под замкнутым itemset понимается такой itemset, для которого не существует суперсета (т.е. сета, включающего наш itemset + другие items) с такой же частотностью (=support).
Тут стоит немного пояснить - до сего момента мы рассматривали просто частые (frequent) itemsets. Существует также понятие *замкнутых* (см. выше) и *максимальных*. Максимальный itemset - это такой itemset, для которого не существует частого (=frequent) суперсета.
Отношения между этими тремя видами itemsets представлено на картинке ниже
AprioriDP (Deep Programming) - позволяет хранить $supp$ в специальной структруе данных, работает немного быстрее классичсекого Apriori
FP Bonsai - улучшенный FP-Growth с обрезкой префиксного дерева (пример алгоритма с *ограничениями*)
Серия Multi-Relations алгоритмов, которые определают несколько связей в itemsets. и другие
В заключении не можем не упомянуть о сумрачном гении ARL докторе Кристиане Боргельте из Университета Констанца (http://www.borgelt.net/software.html). Кристиан реализовывал упомянутые нами алгоритмы на С, Python, Java и R. Ну или почти все. Существует даже GUI за его авторством, где в пару кликов можно загрузить датасет, выбрать нужный алгоритм и найти правила. Это при условии, что оно у вас заработает:) Для простых же задач достаточно и того, что мы рассмотрели в этой статье. А если недостаточно - призываем писать реализацию самим!
Использованная литература: