176 |
Глава 6. Алгоритмы машинного обучения без учителя |
Оценка качества правила
Ассоциативные правила оцениваются по трем показателям:
zz поддержка (частота) объектов (Support (frequency) of items); zz достоверность (confidence);
zzлифт (lift).
Давайте рассмотрим их более подробно.
Поддержка
Поддержка (support) — это количественная оценка того, насколько часто в на шем наборе данных встречается искомая закономерность. Она рассчитывается путем подсчета повторений интересующего нас шаблона, после чего результат делится на общее количество всех транзакций.
Давайте рассмотрим следующую формулу для конкретного предметного на бора itemseta:
numItemseta = Количество транзакций, содержащих itemsetа numtotal = Общее количество транзакций
Просто взглянув на поддержку, мы можем получить представление о том, насколько часто встречается тот или иной шаблон. Низкая под держка означает, что мы ищем редкое явление.
Например, если itemseta = {helmet,ball} появляется в двух транзакциях из шести, то support(itemseta) = 2/6 = 0.33.
Достоверность
Достоверность (confidence) — это число, которое количественно определяет, насколько сильно мы можем связать левую часть правила (X) с правой ча стью (Y), вычисляя условную вероятность. Это вероятность того, что событие X приведет к событию Y, с учетом того, что событие X произошло.
Поиск ассоциативных правил |
177 |
Представим с точки зрения математики правило X Y.
Достоверность этого правила представлена как confidence(X Y) и измеряется следующим образом:
Например, рассмотрим следующее правило:
{helmet, ball} {wickets}.
Достоверность этого правила рассчитывается по следующей формуле:
Это означает, что если у кого-то в корзине есть шлем и мячи {helmet, balls}, то существует 50-процентная вероятность (или 0.5) того, что в ней также окажут ся и ворота для крикета {wickets}.
Лифт
Другой способ оценить качество правила — это рассчитать его лифт (lift). Лифт показывает, насколько качественно правило прогнозирует результат по сравне нию с простым предположением о результате в правой части уравнения. Если предметные наборы X и Y независимы, то лифт рассчитывается следующим образом:
Алгоритмы анализа ассоциаций
В этом разделе мы рассмотрим два алгоритма, которые можно использовать для анализа ассоциаций:
zz априорный алгоритм (apriori algorithm). Предложен Р. Агравалом и Р. Шри кантом в 1994 году;
178 |
Глава 6. Алгоритмы машинного обучения без учителя |
zzалгоритм FP-роста (FP-growth algorithm). Усовершенствование, предложен ное Дж. Ханом и другими в 2001 году.
Давайте рассмотрим каждый из этих алгоритмов.
Априорный алгоритм
Априорный алгоритм — это итеративный и многофазный алгоритм, используе мый для генерации правил ассоциации. Он основан на подходе, включающем в себя генерацию и тестирование.
Перед выполнением априорного алгоритма нам необходимо определить две
переменные: supportthreshold и confidencethreshold (порог поддержки и порог достовер ности).
Алгоритм состоит из двух этапов:
zz Этап генерации кандидатов. На данном этапе генерируются множества на боров предметов (кандидатов), куда входят наборы со значением поддержки, превышающим порог (supportthreshold).
zzЭтап фильтрации. Алгоритм отфильтровывает все правила ниже ожидае мого значения порога достоверности (confidencethreshold).
После фильтрации результирующие правила предлагаются в качестве решения.
Ограничения априорного алгоритма
Главным узким местом априорного алгоритма является генерация правил-кан дидатов на этапе 1 — например, p = {item1, item2, ..., itemm} может создать 2m воз можных предметных наборов. Из-за своей многофазной структуры алгоритм сначала генерирует наборы предметов, а затем ищет среди них те, которые встречаются часто. Это ограничивает производительность и делает априорный алгоритм непригодным для больших объемов данных.
Алгоритм FP-роста
Алгоритм FP-роста (FP-growth algorithm; FP — frequent pattern — частый ша блон) — это усовершенствование априорного алгоритма. Он представляет частые транзакции в виде упорядоченного FP-дерева. Алгоритм состоит из двух этапов:
zz создание FP-дерева; zzпоиск частых шаблонов.
Разберем эти шаги подробно.
Поиск ассоциативных правил |
179 |
Создание FP-дерева
Давайте рассмотрим данные транзакций, отраженные в табл. 6.4. Сначала пред ставим их в виде разреженной матрицы.
Таблица 6.4
ID |
Bat |
Wickets |
Pads |
Helmet |
Ball |
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
2 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
3 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
4 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
Вычислим частоту предметов и отсортируем их в порядке убывания (табл. 6.5).
Таблица 6.5
Предмет |
Частота |
|
|
pads |
3 |
|
|
helmet |
3 |
|
|
bat |
2 |
|
|
wicket |
2 |
|
|
ball |
1 |
|
|
Теперь изменим порядок данных о транзакциях в зависимости от частоты (табл. 6.6).
Таблица 6.6
Транзакция |
Исходные предметы |
Упорядоченные предметы |
|
|
|
t1 |
Wickets, pads |
Pads, wickets |
|
|
|
t2 |
Bat, wickets, pads, helmet |
Helmet, pads, wickets, bat |
|
|
|
t3 |
Helmet, ball |
Helmet, ball |
|
|
|
t4 |
Bat, pads, helmet |
Helmet, pads, bat |
|
|
|
180 |
Глава 6. Алгоритмы машинного обучения без учителя |
Чтобы построить FP-дерево, начнем с его первой ветви. FP-дерево начинается с Null в качестве корня. Для начала представим каждый предмет в виде узла (на рис. 6.17, отображена первая транзакция t1). Обратите внимание, что метка каждого узла — это название предмета, а его частота добавляется после двоето чия. Например, предмет pads имеет частоту 1.
Null
pads:1
wickets:1
t1: {pads, wickets}
ID |
bat |
wickets |
pads |
helmet |
ball |
1 |
0 |
1 |
1 |
0 |
0 |
2 |
1 |
1 |
1 |
1 |
0 |
3 |
0 |
0 |
0 |
1 |
1 |
4 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
Рис. 6.17 |
|
|
Используя тот же принцип, отобразим все четыре транзакции. В результате у нас получится полное FP-дерево. FP-дерево имеет четыре концевых узла, каждый из которых представляет предметный набор, связанный с одной из четырех транзакций. Мы должны вычислить частоту каждого элемента и увеличить ее при многократном использовании — например, при добавлении t2 в FP-дерево
Поиск ассоциативных правил |
|
|
181 |
|||
частота helmet увеличивается до двух. Аналогично, при добавлении t4 она будет |
||||||
еще раз увеличена — до трех. Полученное дерево показано на следующей схеме |
||||||
(рис. 6.18). |
|
|
|
|
|
|
|
|
|
Null |
|
|
|
|
|
|
pads:1 |
helmet:3 |
|
|
|
|
|
|
|
|
|
|
|
|
wickets:1 |
|
|
pads:2 |
|
|
|
|
|
|
|
|
|
|
t1: {pads, wickets} |
bat:1 |
|
ball:1 |
|
|
|
|
t2: {helmet,pads,wicket,bat} |
wickets:1 |
|
|
|
|
|
|
|
t3: {helmet,ball} |
ID |
bat |
wickets |
pads |
helmet |
ball |
|
1 |
0 |
1 |
1 |
0 |
0 |
|
2 |
1 |
1 |
1 |
1 |
0 |
|
3 |
0 |
0 |
0 |
1 |
1 |
|
4 |
1 |
0 |
1 |
1 |
0 |
bat:1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
t4: {helmet,pads,bat} |
|
|
|
|
Рис. 6.18 |
|
|
Обратите внимание, что FP-дерево, сгенерированное на схеме, является упоря |
||||||
доченным. |
|
|
|
|
|
|
Поиск частых шаблонов |
|
|
|
|||
Второй этап алгоритма FP-роста заключается в извлечении частых шаблонов из FP-дерева. Создавая упорядоченное дерево, мы стремимся к эффективной структуре данных, по которой можно легко перемещаться в поисках частых шаблонов.
Мы начинаем с концевого узла и движемся вверх — например, начнем с одного из таких узлов, bat. Затем нужно найти условный базовый шаблон (conditional pattern base) для bat. Он рассчитывается путем указания всех путей от конце вого узла до вершины. Условный базовый шаблон для bat будет выглядеть следующим образом (табл. 6.7).
182 |
|
Глава 6. Алгоритмы машинного обучения без учителя |
|
Таблица 6.7 |
|
|
|
|
|
|
|
Wicket: 1 |
Pads: 1 |
|
Helmet: 1 |
|
|
|
|
Pads: 1 |
Helmet: 1 |
|
|
|
|
|
|
Частый шаблон для bat будет следующий:
{wicket, pads, helmet} : bat {pads,helmet} : bat
Реализация алгоритма FP-роста на Python
В этом разделе мы научимся генерировать ассоциативные правила, используя алгоритм FP-роста на Python. Для этого нам понадобится библиотека pyfpgrowth. Если вы ранее не использовали pyfpgrowth, установите ее:
!pip install pyfpgrowth
Затем импортируем библиотеки, которые потребуются для реализации алго ритма:
import pandas as pd import numpy as np import pyfpgrowth as fp
Далее введем входные данные в transactionSet:
dict1 = { 'id':[0,1,2,3],
'items':[["wickets","pads"],
["bat","wickets","pads","helmet"],
["helmet","pad"],
["bat","pads","helmet"]]
}
transactionSet = pd.DataFrame(dict1)
Как только входные данные введены, сгенерируем шаблоны, которые основаны на параметрах, переданных в find_frequent_patterns(). Обратите внимание, что вторым параметром для функции служит минимальная поддержка, которая в данном случае равна 1:
patterns = fp.find_frequent_patterns(transactionSet['items'],1)
Шаблоны сгенерированы. Теперь выведем их. В шаблонах перечислены комби нации предметов и указана их поддержка (рис. 6.19).
Поиск ассоциативных правил |
183 |
|
|
|
|
|
|
|
Рис. 6.19
Далее сгенерируем правила (рис. 6.20).
Рис. 6.20
Каждое правило имеет левую и правую стороны, разделенные двоеточием (:). Здесь также указаны значения поддержки для каждого правила.