Основные понятия ассоциативного анализа
Ассоциативный анализ: находите интересные взаимосвязи в крупномасштабных наборах данных.
Наборы часто встречающихся элементов. Коллекция элементов, которые часто появляются в части, то есть коллекция, содержащая 0 или более элементов, называется набором элементов.
Поддержка (Support): Доля записей, содержащих набор элементов в наборе данных, для набора элементов.
Уверенность: когда появляются определенные элементы, вероятность появления других элементов для правил.
Правила ассоциации: подразумевают, что между двумя элементами может быть сильная связь. Выражение в виде A->B, мера правила A->B включает в себя поддержку и доверие
Поддержка набора элементов: процентное соотношение количества вхождений набора элементов к количеству всех вещей в наборе данных называется поддержкой набора элементов.
eg:support(A⇒B)=support_count(A∪B)/N
Степень поддержки отражает вероятность одновременного появления А и В, а степень поддержки ассоциативного правила равна степени поддержки частого набора.
Достоверность набора элементов: процент наборов данных, содержащих A, которые содержат B
eg:confidence(A⇒B)=support_count(A∪B)/support_count(A)
Уверенность отражает вероятность того, что транзакция содержит B, если она содержит A в транзакции. Ее также можно назвать вероятностью появления В при условии, что происходит А, которая называется условной вероятностью.
Пользователей интересуют только правила ассоциации с более высокой поддержкой и достоверностью (достоверностью).
Этапы анализа ассоциации
1. Найти частые наборы, т. е. вычислить поддержку всех возможных комбинаций, и найти набор, который не меньше минимального набора поддержки, заданного искусственно.
2. Обнаружить ассоциативные правила, т. е. вычислить уровень достоверности множества, который не меньше минимальной степени поддержки, установленной искусственно, и найти правило минимального уровня достоверности, которое не меньше установленного минимального уровня достоверности.
Два вида отношений в ассоциативном анализе: простая ассоциация и ассоциация последовательности
Простые отношения:
Простую корреляцию можно проанализировать на примере классических покупок. 80% покупателей, которые покупают хлеб, купят молоко. Поскольку хлеб и молоко необходимы для завтрака, их сочетание составляет неотъемлемую часть завтрака. Это простая корреляция.
Отношения последовательности:
Когда вы покупаете новый мобильный телефон, вы рассмотрите вопрос о покупке аксессуаров для мобильных телефонов, таких как пленка для мобильного телефона. Это последовательность отношений. Вы не будете сначала покупать пленку для мобильного телефона, а затем покупать мобильный телефон. Связь очень очевидна. Это Отношение является разновидностью отношения последовательности.Последовательное отношение, то есть последовательное отношение.
Правила ассоциации: правило — это стандарт для измерения вещей, то есть алгоритм.
Алгоритм простых правил ассоциации
Фонд алгоритмической мысли
Если набор элементов является частым, то все его подмножества также являются частыми. Чаще используется его обратное утверждение отрицания, что если набор элементов нечастый, то все его надмножества также нечасты.
Простые ассоциативные правила — это неконтролируемые методы обучения, направленные на изучение внутренних структур. Простые правила ассоциации также являются наиболее часто используемыми технологиями. Основные алгоритмы включают: Apriori, GRI и Carma. Среди них Apriori и Carma в основном улучшают эффективность анализа правил ассоциации, в то время как GRI фокусируется на том, как расширить ассоциацию одного понятия. уровня к более понятийным уровням отношений, а затем выявить внутреннюю структуру вещей.
Форма хранения данных простых правил ассоциации: один формат данных транзакции, а другой формат данных таблицы.
Алгоритм правила ассоциации последовательностей
Суть правил ассоциации последовательностей заключается в том, чтобы найти корреляцию до и после развития вещей.Изучение ассоциации последовательностей может предсказать будущее развитие вещей, а также распределить и упорядочить вещи в соответствии с предсказанным развитием.
Как установить разумную поддержку и доверие?
По определенному правилу :(A=a)−>(B=b)
(поддержка=30%, достоверность=60%); где поддержка=30% означает, что во всех записях данных вероятность одновременного появления A=a и B=b составляет 30%; достоверность=60% означает, что в все записи данных. В случае A=a вероятность появления B=b составляет 60%, что является условной вероятностью. Поддержка показывает вероятность того, что A=a и B=b появятся одновременно, а достоверность показывает вероятность того, что B=b появится, когда появится A=a.
(1) Если закрытые значения поддержки и уверенности установлены слишком высокими, хотя время майнинга может быть сокращено, легко привести к игнорированию некоторых нечастых признаков, неявно выраженных в данных, и трудно найти достаточно полезные правила;
(2) Если закрытые значения поддержки и достоверности установлены слишком низкими, может быть сгенерировано слишком много правил и даже может быть сгенерировано большое количество избыточных и недействительных правил.В то же время из-за присущих проблем алгоритма, это приведет к высокой нагрузке на вычисления, что сильно увеличит время майнинга.
Применение ассоциативного анализа
(1): Анализ покупательской корзины путем проверки того, какие продукты часто продаются вместе, может помочь магазинам понять покупательское поведение пользователей. Это извлечение из океана данных может использоваться только для ценообразования продуктов, продвижения на рынке, управления запасами и других ссылок.
(2): Нашел несколько общих слов в ленте Twitter. Для заданного поискового запроса найдите набор слов, которые часто встречаются в твитах.
(3): Извлечение новостных трендов из потока кликов на новостных веб-сайтах и определение того, какие новости широко просматриваются пользователями.
(4): Рекомендация поисковой системы, рекомендует связанные термины запроса, когда пользователь вводит запрос.
(5): Были обнаружены аналогичные характеристики ядовитых грибов. Здесь нас интересуют только те наборы, которые содержат определенный элемент признака (токсин), найти некоторые общие признаки ядовитых грибов и использовать эти признаки, чтобы избежать позднего появления ядовитых грибов.
(6): Книжная рекомендация библиотечной информации, информация о заимствовании студентов и ситуация с заимствованием студентов разных специальностей, анализ ситуации с заимствованием у разных студентов и выработка ряда рекомендаций.
(7): Рекомендация информации об уведомлениях о новостях в сети кампуса, в процессе сбора информации об уведомлениях о новостях в сети кампуса, анализ разницы в информации о новостях в разных отделах и колледжах и рекомендации новостей в процессе просмотра информации о новостях.
Априорный алгоритм
Предположим, у нас есть продуктовый магазин, в котором есть 4 товара (товар 0, товар 1, товар 2 и товар 3), и на графике 2 показаны все возможные комбинации между всеми товарами:
Для поддержки одного набора элементов мы можем вычислить его, перебирая каждую запись и проверяя, содержит ли запись набор элементов. Для набора данных, содержащего всего N элементов 2
N
−1
Нереально повторить описанный выше процесс расчета для комбинации наборов товаров.
Исследователи обнаружили так называемый принцип априори, который может помочь нам сократить объем вычислений. Принцип Априори гласит, что если набор элементов является частым, то все его подмножества также являются частыми. Чаще используется его обратное утверждение отрицания, что если набор элементов нечастый, то все его надмножества также нечасты.
Примечание. Подмножество здесь — это не подмножество в традиционной математике, а набор дочерних элементов. Например, набор часто используемых элементов содержит 3 элемента, тогда набор элементов, состоящий из подмножеств этих трех элементов, должен быть набором часто используемых элементов.
Известно, что на рисунке 3 теневые наборы элементов {2,3} встречаются нечасто. Используя это знание, мы знаем, что наборы элементов {0,2,3}, {1,2,3} и {0,1,2,3} также нечасты. То есть, как только рассчитана поддержка {2,3} и известно, что это нечасто, {0,2,3}, {1,2,3} и {0,1, 2,3} .
Алгоритм априори — это метод поиска часто встречающихся наборов элементов.
Двумя входными параметрами алгоритма Apriori являются минимальная поддержка и набор данных. Алгоритм сначала генерирует список наборов всех отдельных элементов. Затем набор данных сканируется, чтобы увидеть, какие наборы элементов удовлетворяют минимальным требованиям поддержки, а те наборы, которые не соответствуют минимальным требованиям, удаляются. Затем оставшиеся наборы объединяются для создания набора из двух элементов. Затем записи транзакций повторно сканируются для удаления наборов элементов, которые не удовлетворяют минимальной поддержке. Этот процесс повторяется до тех пор, пока не будут удалены все наборы элементов.
Алгоритм должен постоянно искать наборы-кандидаты, а затем сокращать, чтобы удалить наборы-кандидаты нечастых подмножеств.Временная сложность - это экспоненциальный уровень насильственного перечисления всех подмножеств.O(n2) Это будет полиномиальный уровень, а конкретные коэффициенты полинома определяются базовой реализацией.
Алгоритм Ариори состоит из двух основных шагов:
1. Соединение: (соедините наборы элементов попарно, чтобы сформировать новый набор кандидатов) Используйте часто встречающиеся наборы из k элементов, которые были найдены.Lk, набор кандидатов получается попарным соединениемCk+1, обратите внимание на связьLk[i],Lk[j], должно быть k-1 значений атрибута с одинаковым значением, а затем два других разных распределенияLk[i],Lk[j], получается вот такCk+1 заLk+1 за набор кандидатов.
2. Сокращение: (удалить нечастые наборы элементов) набор кандидатовCkНе все часто встречающиеся наборы элементов в +1 должны быть сокращены и удалены, чем раньше, тем лучше, чтобы предотвратить обработку все большего количества недействительных элементов данных.Только когда подмножества представляют собой все наборы-кандидаты частых наборов, являются частыми наборами, что является основой для сокращения..
Реализация алгоритма
from numpy import *
def loadDataSet():return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
# 获取候选1项集，dataSet为事务集。返回一个list，每个元素都是set集合
def createC1(dataSet):
C1 = [] # 元素个数为1的项集（非频繁项集，因为还没有同最小支持度比较）for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort() # 这里排序是为了，生成新的候选集时可以直接认为两个n项候选集前面的部分相同# 因为除了候选1项集外其他的候选n项集都是以二维列表的形式存在，所以要将候选1项集的每一个元素都转化为一个单独的集合。return list(map(frozenset, C1)) #map(frozenset, C1)的语义是将C1由Python列表转换为不变集合（frozenset，Python中的数据结构）
# 找出候选集中的频繁项集
# dataSet为全部数据集，Ck为大小为k（包含k个元素）的候选项集，minSupport为设定的最小支持度
def scanD(dataSet, Ck, minSupport):
ssCnt = {} # 记录每个候选项的个数for tid in dataSet:
for can in Ck:
if can.issubset(tid):
ssCnt[can] = ssCnt.get(can, 0) + 1 # 计算每一个项集出现的频率
numItems = float(len(dataSet))
retList = []
supportData = {}
for key in ssCnt:
support = ssCnt[key] / numItems
if support >= minSupport:
retList.insert(0, key) #将频繁项集插入返回列表的首部
supportData[key] = support
return retList, supportData #retList为在Ck中找出的频繁项集（支持度大于minSupport的），supportData记录各频繁项集的支持度
# 通过频繁项集列表Lk和项集个数k生成候选项集C(k+1)。
def aprioriGen(Lk, k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i + 1, lenLk):
# 前k-1项相同时，才将两个集合合并，合并后才能生成k+1项
L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2] # 取出两个集合的前k-1个元素
L1.sort(); L2.sort()
if L1 == L2:
retList.append(Lk[i] | Lk[j])
return retList
# 获取事务集中的所有的频繁项集
# Ck表示项数为k的候选项集，最初的C1通过createC1()函数生成。Lk表示项数为k的频繁项集，supK为其支持度，Lk和supK由scanD()函数通过Ck计算而来。
def apriori(dataSet, minSupport=0.5):
C1 = createC1(dataSet) # 从事务集中获取候选1项集
D = list(map(set, dataSet)) # 将事务集的每个元素转化为集合
L1, supportData = scanD(D, C1, minSupport) # 获取频繁1项集和对应的支持度
L = [L1] # L用来存储所有的频繁项集
k = 2while (len(L[k-2]) > 0): # 一直迭代到项集数目过大而在事务集中不存在这种n项集
Ck = aprioriGen(L[k-2], k) # 根据频繁项集生成新的候选项集。Ck表示项数为k的候选项集
Lk, supK = scanD(D, Ck, minSupport) # Lk表示项数为k的频繁项集，supK为其支持度
L.append(Lk);supportData.update(supK) # 添加新频繁项集和他们的支持度
k += 1return L, supportData
if __name__=='__main__':
dataSet = loadDataSet() # 获取事务集。每个元素都是列表# C1 = createC1(dataSet) # 获取候选1项集。每个元素都是集合# D = list(map(set, dataSet)) # 转化事务集的形式，每个元素都转化为集合。# L1, suppDat = scanD(D, C1, 0.5)# print(L1,suppDat)
L, suppData = apriori(dataSet,minSupport=0.7)
print(L,suppData)
Алгоритм роста FP для эффективного поиска часто встречающихся наборов элементов
Деревья FP: эффективный способ кодирования наборов данных
Алгоритм роста FP хранит данные в компактной структуре данных, называемой деревом FP. FP означает частый шаблон. Дерево FP похоже на другие древовидные структуры в информатике, но оно соединяет аналогичные элементы через ссылки, а элементы связанных элементов можно рассматривать как связанный список.
В отличие от деревьев поиска, элемент может появляться в дереве FP несколько раз. В дереве FP будет храниться частота наборов элементов, и каждый набор элементов будет храниться в виде числа в виде пути. Узел дерева дает один элемент в наборе и его количество вхождений в последовательности, а путь дает количество вхождений в последовательности.
Ссылки между похожими элементами называются ссылками узлов и используются для быстрого поиска местоположения похожих элементов.
На рисунке ниже показан пример дерева FP.
набор транзакций
Идентификатор транзакции Элемент элемента в транзакции
001 r, z, h, j, p
002 z, y, x, w, v, u, t, s
003 z
004 r, x, n, o, s
005 y, r, x, z, q, t, p
006 y, z, x, e, q, s, t, m
Сгенерированное дерево FP
Интерпретация дерева FP:
На рисунке элемент элемента z встречается 5 раз, а набор {r, z} — 1 раз. Таким образом, можно сделать вывод, что z должен встречаться 4 раза сам по себе или с другими символами. Набор {t, s, y, x, z} появляется дважды, набор {t, r, y, x, z} появляется один раз, а сам z появляется один раз. Точно так же способ чтения дерева FP состоит в том, чтобы прочитать путь от узла к корневому узлу. Элементы на пути составляют частый набор элементов, а значение начального узла представляет поддержку этого набора элементов. Согласно рисунку 5, мы можем быстро прочитать, что набор элементов {z} имеет степень поддержки 5, набор элементов {t, s, y, x, z} имеет степень поддержки 2, а набор элементов {r, y , x, z} Поддержка равна 1, набор элементов {r, s, x} имеет носитель 1. Один и тот же элемент элемента будет появляться в дереве FP несколько раз, в том числе потому, что один и тот же элемент элемента будет существовать в нескольких путях, образуя несколько часто встречающихся наборов элементов. Но общие пути часто встречающихся наборов элементов объединяются, как показано на рисунке {t, s, y, x, z} и {t, r, y, x, z}.
Как и прежде, мы берем минимальный порог, и элементы, число вхождений которых ниже минимального порога, будут напрямую игнорироваться. На рисунке минимальная поддержка установлена равной 3, поэтому q и p не отображаются в FP.
Рабочий процесс алгоритма роста FP выглядит следующим образом. Сначала постройте дерево FP, а затем используйте его для поиска часто используемых наборов элементов. Чтобы построить дерево FP, необходимо дважды отсканировать исходный набор данных. Первый проход подсчитывает количество вхождений всех элементов элемента. Первый проход базы данных используется для подсчета частоты появления, а второй проход учитывает только эти частые элементы.
Основной процесс поиска часто встречающихся наборов элементов с помощью алгоритма роста FP выглядит следующим образом:
- Построить дерево FP
- Добыча частых наборов предметов из дерева FP
Таблица головных указателей
Алгоритму FP-роста также требуется структура данных, называемая таблицей головных указателей, которая на самом деле очень проста.Это массив, используемый для записи общего количества вхождений каждого элемента элемента, и указатель на первый узел элемента элемента. в дереве ФП прилагается. Таким образом, каждый элемент элемента представляет собой односвязный список. Описание иллюстрации:
Здесь словарь Python используется в качестве структуры данных для хранения таблицы указателей головок. Вводится по имени элемента элемента, содержит общее количество вхождений и указатель на первый подобный элемент элемента.
При первом обходе набора данных будет получена частота появления каждого элемента элемента, удалены элементы элемента, которые не соответствуют минимальной поддержке, и сгенерирована эта таблица указателей головок.
Порядок элементов элемента
Как упоминалось выше, деревья FP объединяют одни и те же часто встречающиеся наборы элементов (или одни и те же части). Следовательно, чтобы судить о сходстве двух наборов элементов, элементы наборов элементов необходимо отсортировать (но для этого есть другие причины, и есть другие преимущества). Сортировка основана на абсолютной частоте появления (общее количество случаев) элементов элемента. При втором обходе набора данных каждый набор элементов считывается (читается), элементы, не удовлетворяющие минимальной поддержке, удаляются (фильтруются), а элементы сортируются (переупорядочиваются).
Построить дерево FP
После фильтрации и сортировки записей транзакций можно построить дерево FP. Начиная с пустого набора, отфильтрованные и переупорядоченные наборы частых элементов добавляются в дерево по одному. Если существующий элемент уже существует в дереве, увеличьте значение существующего элемента; если существующий элемент не существует, добавьте ветвь к дереву. Процесс добавления первых двух транзакций:
Процесс реализации
Вход: набор данных, минимальный масштаб
Выход: дерево FP, таблица головных указателей
1. Просмотрите набор данных, подсчитайте количество вхождений каждого элемента и создайте таблицу указателей головок.
2. Удалите элементы в таблице указателей головы, которые не соответствуют минимальному масштабу.
3. Пройдитесь по набору данных во второй раз, чтобы создать дерево FP. Для наборов элементов в каждом наборе данных:
3.1 Инициализация пустого дерева FP
3.2 Фильтрация и изменение порядка каждого набора элементов
3.3 Используйте этот набор элементов для обновления дерева FP, начиная с корневого узла дерева FP:
3.3.1 Если первый элемент текущего набора элементов существует в дочернем узле текущего узла дерева FP, обновить значение счетчика этого дочернего узла
3.3.2 В противном случае создайте новый дочерний узел и обновите таблицу головных указателей.
3.3.3 Процесс рекурсии 3.3 для оставшихся элементов текущего набора элементов и соответствующих дочерних узлов текущего элемента элемента
Добыча частых наборов предметов из дерева FP
Три основных шага для извлечения часто встречающихся наборов элементов из дерева FP:
- Получить базу условных шаблонов из дерева FP;
- Построить условное дерево FP, используя базы условных шаблонов;
- Итеративно повторяйте шаги 1 и 2, пока дерево не будет содержать один элемент элемента.
где «база условного шаблона» — это набор путей, заканчивающихся искомым элементом. Каждый путь на самом деле является префиксным путем. Короче говоря, префиксный путь — это все, что находится между искомым элементом и корневым узлом дерева.
Например
Тогда основа условного шаблона каждого элемента частого элемента:
путь префикса часто используемого элемента
z {}: 5
r {x, s}: 1, {z, x, y}: 1, {z}: 1
x {z}: 3, {}: 1
y {z, x}: 3
s {z, x, y}: 2, {x}: 1
t {z, x, y, s}: 2, {z, x, y, r}: 1
Вы нашли шаблон? z существует в пути {z}, поэтому путь префикса пуст, и добавляется еще один элемент, значение счетчика узла z в пути равно 5, чтобы сформировать его условную базу шаблона; r существует в пути {r, z}, {In r, y, x, z}, {r, s, x} получают префиксные пути {z}, {y, x, z}, {s, x} соответственно, и добавить значение счетчика узла r в соответствующем пути (оба 1) образуют основу условного шаблона r и так далее.
Создайте условное дерево FP
Для каждого частого элемента создается условное дерево FP. Эти деревья могут быть построены с помощью одного и того же кода построения дерева, используя базы условных шаблонов, только что обнаруженные в качестве входных данных. Например, для r, то есть с «{x, s}: 1, {z, x, y}: 1, {z}: 1» на входе, вызовите функцию createTree() для получения условного дерева FP of r; для t Входными данными является соответствующий базис условного шаблона "{z, x, y, s}: 2, {z, x, y, r}: 1".
Рекурсивный поиск часто встречающихся наборов элементов
С деревом FP и условным деревом FP мы можем рекурсивно находить часто встречающиеся наборы элементов на основе первых двух шагов.
Рекурсивный процесс выглядит следующим образом:
Вход: у нас есть дерево FP текущего набора данных (inTree, headerTable)
1. Инициализируйте префикс пустого списка для представления префикса
2. Инициализируйте пустой список freqItemList для получения сгенерированных наборов частых элементов (в качестве вывода).
3. Для каждого элемента basePat в таблице заголовков (в порядке возрастания значения счетчика) рекурсивно:
3.1 Обратите внимание, что basePat + preFix является текущим частым набором элементов newFreqSet
3.2 Добавьте newFreqSet в freqItemList
3.3 Вычислить условное дерево FP для t (myCondTree, myHead)
3.4 Если условное дерево FP не пусто, перейти к следующему шагу, иначе выйти из рекурсии
3.4 Возьмите myCondTree и myHead в качестве новых входных данных, newFreqSet в качестве нового префикса, плюс freqItemList и повторите этот процесс.
код реализации
# FP树类
class treeNode:def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue #节点元素名称，在构造时初始化为给定值
self.count = numOccur # 出现次数，在构造时初始化为给定值
self.nodeLink = None # 指向下一个相似节点的指针，默认为None
self.parent = parentNode # 指向父节点的指针，在构造时初始化为给定值
self.children = {} # 指向子节点的字典，以子节点的元素名称为键，指向子节点的指针为值，初始化为空字典
# 增加节点的出现次数值def inc(self, numOccur):
self.count += numOccur
# 输出节点和子节点的FP树结构def disp(self, ind=1):
print(' ' * ind, self.name, ' ', self.count)
for child in self.children.values():
child.disp(ind + 1)
# =======================================================构建FP树==================================================
# 对不是第一个出现的节点，更新头指针块。就是添加到相似元素链表的尾部
def updateHeader(nodeToTest, targetNode):while (nodeToTest.nodeLink != None):
nodeToTest = nodeToTest.nodeLink
nodeToTest.nodeLink = targetNode
# 根据一个排序过滤后的频繁项更新FP树
def updateTree(items, inTree, headerTable, count):if items[0] in inTree.children:
# 有该元素项时计数值+1
inTree.children[items[0]].inc(count)
else:
# 没有这个元素项时创建一个新节点
inTree.children[items[0]] = treeNode(items[0], count, inTree)
# 更新头指针表或前一个相似元素项节点的指针指向新节点if headerTable[items[0]][1] == None: # 如果是第一次出现，则在头指针表中增加对该节点的指向
headerTable[items[0]][1] = inTree.children[items[0]]
else:
updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
if len(items) > 1:
# 对剩下的元素项迭代调用updateTree函数
updateTree(items[1::], inTree.children[items[0]], headerTable, count)
# 主程序。创建FP树。dataSet为事务集，为一个字典，键为每个事物，值为该事物出现的次数。minSup为最低支持度
def createTree(dataSet, minSup=1):# 第一次遍历数据集，创建头指针表
headerTable = {}
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
# 移除不满足最小支持度的元素项
keys = list(headerTable.keys()) # 因为字典要求在迭代中不能修改，所以转化为列表for k in keys:
if headerTable[k] < minSup:
del(headerTable[k])
# 空元素集，返回空
freqItemSet = set(headerTable.keys())
if len(freqItemSet) == 0:
return None, None# 增加一个数据项，用于存放指向相似元素项指针for k in headerTable:
headerTable[k] = [headerTable[k], None] # 每个键的值，第一个为个数，第二个为下一个节点的位置
retTree = treeNode('Null Set', 1, None) # 根节点# 第二次遍历数据集，创建FP树for tranSet, count in dataSet.items():
localD = {} # 记录频繁1项集的全局频率，用于排序for item in tranSet:
if item in freqItemSet: # 只考虑频繁项
localD[item] = headerTable[item][0] # 注意这个[0]，因为之前加过一个数据项if len(localD) > 0:
orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 排序
updateTree(orderedItems, retTree, headerTable, count) # 更新FP树return retTree, headerTable
# =================================================查找元素条件模式基===============================================
# 直接修改prefixPath的值，将当前节点leafNode添加到prefixPath的末尾，然后递归添加其父节点。
# prefixPath就是一条从treeNode（包括treeNode）到根节点（不包括根节点）的路径
def ascendTree(leafNode, prefixPath):if leafNode.parent != None:
prefixPath.append(leafNode.name)
ascendTree(leafNode.parent, prefixPath)
# 为给定元素项生成一个条件模式基（前缀路径）。basePet表示输入的频繁项，treeNode为当前FP树中对应的第一个节点
# 函数返回值即为条件模式基condPats，用一个字典表示，键为前缀路径，值为计数值。
def findPrefixPath(basePat, treeNode):
condPats = {} # 存储条件模式基while treeNode != None:
prefixPath = [] # 用于存储前缀路径
ascendTree(treeNode, prefixPath) # 生成前缀路径if len(prefixPath) > 1:
condPats[frozenset(prefixPath[1:])] = treeNode.count # 出现的数量就是当前叶子节点的数量
treeNode = treeNode.nodeLink # 遍历下一个相同元素return condPats
# =================================================递归查找频繁项集===============================================
# 根据事务集获取FP树和频繁项。
# 遍历频繁项，生成每个频繁项的条件FP树和条件FP树的频繁项
# 这样每个频繁项与他条件FP树的频繁项都构成了频繁项集
# inTree和headerTable是由createTree()函数生成的事务集的FP树。
# minSup表示最小支持度。
# preFix请传入一个空集合（set([])），将在函数中用于保存当前前缀。
# freqItemList请传入一个空列表（[]），将用来储存生成的频繁项集。
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):# 对频繁项按出现的数量进行排序进行排序
sorted_headerTable = sorted(headerTable.items(), key=lambda p: p[1][0]) #返回重新排序的列表。每个元素是一个元组，[（key,[num,treeNode],()）
bigL = [v[0] for v in sorted_headerTable] # 获取频繁项for basePat in bigL:
newFreqSet = preFix.copy() # 新的频繁项集
newFreqSet.add(basePat) # 当前前缀添加一个新元素
freqItemList.append(newFreqSet) # 所有的频繁项集列表
condPattBases = findPrefixPath(basePat, headerTable[basePat][1]) # 获取条件模式基。就是basePat元素的所有前缀路径。它像一个新的事务集
myCondTree, myHead = createTree(condPattBases, minSup) # 创建条件FP树
if myHead != None:
# 用于测试
print('conditional tree for:', newFreqSet)
myCondTree.disp()
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList) # 递归直到不再有元素
# 生成数据集
def loadSimpDat():
simpDat = [['r', 'z', 'h', 'j', 'p'],
['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
['z'],
['r', 'x', 'n', 'o', 's'],
['y', 'r', 'x', 'z', 'q', 't', 'p'],
['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
return simpDat
# 将数据集转化为目标格式
def createInitSet(dataSet):
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1return retDict
if __name__=='__main__':
minSup =3
simpDat = loadSimpDat() # 加载数据集
initSet = createInitSet(simpDat) # 转化为符合格式的事务集
myFPtree, myHeaderTab = createTree(initSet, minSup) # 形成FP树# myFPtree.disp() # 打印树
freqItems = [] # 用于存储频繁项集
mineTree(myFPtree, myHeaderTab, minSup, set([]), freqItems) # 获取频繁项集
print(freqItems) # 打印频繁项集
Резюме алгоритма роста FP
Алгоритм роста FP — эффективный метод обнаружения частых закономерностей в наборах данных. Алгоритм роста FP использует принцип априори и работает быстрее. Алгоритм Apriori создает наборы элементов-кандидатов, а затем сканирует набор данных, чтобы проверить, являются ли они частыми. Поскольку набор данных сканируется только дважды, алгоритм роста FP работает быстрее. В алгоритме роста FP набор данных хранится в структуре, называемой деревом FP. После того, как дерево FP построено, можно найти частые наборы элементов, найдя условную основу элементов элементов и построив условное дерево FP. Процесс повторяется с условием для большего количества элементов, пока дерево FP не будет содержать только один элемент.
Преимущества и недостатки:
- Преимущества: Обычно быстрее, чем Apriori.
- Недостатки: сложно реализовать, производительность ухудшится на некоторых наборах данных.
- Применимые типы данных: дискретные данные.
Правила ассоциации не всегда интересны
Например, рассмотрим случай с розничным продавцом хлопьев, который провел опрос 5000 студентов. Используется для изучения того, рекомендуется ли завтракать учащимся после того, как они поиграли в баскетбол.
как показывают данные:
60% студентов играют в баскетбол первыми с утра,
75% студентов завтракают таким образом (включая тех, кто завтракает после игры в баскетбол, и тех, кто завтракает без игры в баскетбол)
40% школьников играют в баскетбол и завтракают таким образом.
Предположим, что порог поддержки s=0,4 и доверительный порог c=60%. Основываясь на приведенных выше данных и предположениях, мы можем вывести правило сильной ассоциации «(играть в баскетбол) → (завтракать)», потому что поддержка (игры в баскетбол) и (завтрака) превышает порог поддержки, и они оба являются частыми элементами, в то время как доверие к правилуc=40%
60%
=66.6%
Также больше, чем доверительный порог.
Однако приведенные выше ассоциативные правила легко понять неправильно, потому что доля завтрака составляет 75%, что больше, чем 66%.
То есть вероятность того, что они выберут такой завтрак перед игрой в баскетбол, превышает 75%, но после игры в баскетбол учащиеся не хотят есть такой завтрак или пропускать завтрак. Потому что вероятность того, что студенты съедят такой завтрак после игры в мяч, снизилась до 66%.
Таким образом, игра в баскетбол и завтрак на самом деле имеют отрицательную корреляцию.
Так что сильные ассоциации не обязательно интересны.
Мы должны использовать показатель корреляции (здесь с использованием показателя подъема чтения), чтобы охарактеризовать подъем ассоциации.
этоP(B/A)/P(B)
чтобы указать, лучше ли рекомендовать B в присутствии A, чем рекомендовать B до того, как A не появится.
Формула эквивалентнаlift(A,B)=P(A⋃B)
P(A)P(B)