РезюмеПрофессор Хан Цзявэй и другие предположили, что алгоритм FP-growth (Frequent Pattern Growth) является классическим алгоритмом в области интеллектуального анализа частых паттернов (FP).За его эффективной работой стоит мощное дерево сжатия информации — Frequent Pattern Tree (Frequent Pattern Tree). , FPTree), но легко пропустить некоторые ключевые шаги в процессе построения FPTree, такие как правильное упорядочение частых шаблонов (FPO) и стабильность результатов сортировки.Эта статья начинается с оригинальной статьи и анализирует текущую сеть для неуместность репродукционных статей с высоким кликом, дается более разумный метод репродукции.
введение
Алгоритм роста FP Хана Цзявэя[1]и др., предложенный в 2000 году, в котором FPTree является ключевой структурой данных, которая делает этот алгоритм более эффективным, чем такие алгоритмы, как Aprioris. FPTree сильно сжимает все транзакции (транзакции) в базе данных в пути дерева и все часто встречающиеся элементы (частые элементы), FI) становятся узлом дерева, каждый узел имеет соответствующий счетчик, представляющий количество раз, когда FI появляется в базе данных, где количество конечных узлов равно количеству раз, когда FI появляются на пути прямого обхода. в базе данных. Таким образом, вся работа по майнингу сосредоточена на исходном FPTree, и при построении FPTree основным шагом является сортировка каждой транзакции в порядке убывания.Однако при этом должна быть обеспечена согласованность порядка появления ИФ, иначе структура дерева не будет уникальной, и результаты майнинга будут необъективными.Это момент, который большинство людей склонны игнорировать при воспроизведении, и другая ситуация появляется в популярном бестселлере машинного обучения.«Машинное обучение в действии»(в переводе: Практика машинного обучения),Версия реализации книжного роста FP приводит к случайности.В Интернете я выбрал две повторяющиеся статьи о росте FP с высоким количеством кликов:
-
«Принцип и реализация часто используемых наборов элементов и правил ассоциации FP-growth — IBM»(далее именуемый: Статья 1)
-
«Внедрение алгоритмов машинного обучения с нуля (14) FP-рост — Знание»(далее именуемый: Статья 2)
Эти две статьи очень похожи, и обе относятся к книге «Машинное обучение в действии». Вы можете видеть, насколько широко распространена эта ошибка. Набор данных, используемый в этой статье, такой же, как и в исходной статье о росте FP, а именно:
Правильное FPTree выглядит так:
Затем наборы данных на рисунке 1 были запущены с помощью алгоритмов, предоставленных упомянутыми репродукционными статьями, для анализа их неадекватности. Кроме того, версия языка Python, используемая в этой статье,3.7.6.
Примечание. В этой статье нет злого умысла по отношению к упомянутым книгам или статьям, и она предназначена только для доброкачественного академического обмена и взаимного обучения. В силу моей бездарности и неопытности неизбежны неточности в тексте, будьте вежливы.
Где они не правы?
Из предыдущей статьи мы знаем, что корректность FPTree зависит от ФИ в правильном порядке.Левая часть рисунка 1 — это транзакция в исходной базе данных.Предполагая, что минимальная поддержка равна 3, следующие ФИ могут быть получены после первое сканирование базы данных:
Затем отсортируйте в порядке убывания по количеству вхождений FI,Но действительно ли можно получить такой же результат сортировки, как в правой части рис. 1?Мы сравниваем и тестируем метод прямой сортировки по убыванию и алгоритм, представленный в статье [1, 2].
Используйте прямой метод сортировки по убыванию, чтобы получить результат:
T100 -> f,c,a,m,p
T200 -> c,f,a,b,m
T300 -> f,b
T400 -> c,b,p
T500 -> f,c,a,p,m
непосредственно отсортированные результаты
Существует большая разница с результатами на рисунке 1, и FPTree, сгенерированный такими результатами сортировки, показан на следующем рисунке:
Очевидно, что такой FPTree не может дать правильный результат. Этот метод игнорирует два важных звена при создании FPTree, которые описаны в оригинальной статье следующим образом:
(3) If multiple transactions share an identical frequent item set, they can be merged into one with the number of occurrences registered as count. It is easy to check whether two sets are identical if the frequent items in all of the transactions are sorted according to a fixed order. (4) If two transactions share a common prefix, according to some sorted order of frequent items, the shared parts can be merged using one prefix structure as long as the count is registered properly. If the frequent items are sorted in their frequency descending order, there are better chances that more prefix strings can be shared.
Правило (3) гласит, что если несколько транзакций используют одни и те же FI, их порядок должен быть постоянным.
Суть в том, чтобы разделить ФИ, тогда все они должны быть выражены в виде
. Правило (4) гласит, что если две транзакции имеют одинаковый префикс, то в случае сортировки по убыванию их префиксы также должны совпадать.
иметь общий префикс
, в это время префикс должен оставаться согласованным, то есть он должен начинаться с
как префикс.
Методы статей [1, 2] обсуждаются ниже отдельно.Поскольку все статьи [1, 2] относятся к «Машинному обучению в действии», они, естественно, не будут делать низкоуровневых ошибок, таких как прямая сортировка.Но действительно ли алгоритм, который он предоставляет, совершенен?
Код сортировки, указанный в статье 1:
#scan dataset at the second time, filter out items for each record
for items,count in frozenDataSet.items():
frequentItemsInRecord = {}
for item in items:
if item in frequentItems:
frequentItemsInRecord[item] = headPointTable[item][0]
if len(frequentItemsInRecord) > 0:
# 排序代码
orderedFrequentItems = [v[0] for v in sorted(frequentItemsInRecord.items(), key=lambda v:v[1], reverse = True)]
updateFPTree(fptree, orderedFrequentItems, headPointTable, count)
Код сортировки, предусмотренный статьей 2:
FP_tree = FPNode('root', 1, None) # root node
for record, count in train_data.items():
frequent_item = {}
for item in record: # if item is a frequent set， add it
if item in frequent_set: # 2.1 filter infrequent_item
frequent_item[item] = header[item][0]
if len(frequent_item) > 0:
# 排序代码
ordered_frequent_item = [val[0] for val in sorted(frequent_item.items(), key=lambda val:val[1], reverse=True)] # 2.1 sort all the elements in descending order according to count
self.updataTree(ordered_frequent_item, FP_tree, header, count) # 2.2 insert frequent_item in FP-Tree， share the path with the same prefix
Можно видеть, что идеи сортировки этих двух согласуются (поэтому результат должен быть предоставлен только одному из них).На следующем рисунке показаны результаты сортировки:
На рисунке 3 показаны результаты двух прогонов.Хотя они удовлетворяют требованиям правил (3) и (4), результаты двух сортировок совершенно разные.Такие результаты не влияют на алгоритмы, такие как Apriori, но на FPTree, такие как т.к. это фатально в структуре, чувствительной к порядку, что приведет к двум совершенно разным FPT-деревьям, которые в свою очередь имеют разные Базу условных паттернов и Дерево условных паттернов. Причина в том, что все они используютfrozensetструктура данных, как показано на следующем рисунке:
можно увидеть дваждыfrozensetСохраненные результаты противоречивы, потому чтоfrozensetНе стабильно, см. подробностиStackOverflow: 3812429. Насколько такой подход влияет на результаты? Давайте оценим результаты этих двух алгоритмов, как показано на следующем рисунке:
В результатах, показанных на рисунке 5,
ИФ, полученные двумя сортировками, полностью несовместимы из-за случайности, и правильные ИФ в исходной статье показаны на следующем рисунке:
И независимо от того, какой результат запуска начинается с
FI для суффикса не включены
,Это относительно неожиданная вещь, возможно, автор не совсем ясно соображал, когда использовал структуры данных, предоставляемые разными языками, но идею все же стоит изучить. Чтобы полностью воспроизвести результаты исходного текста, одна из моих незрелых идей состоит в том, чтобы отброситьsetЭта удобная, но неустойчивая структура, замененнаяlistилиtuple.
незрелая попытка
Здесь я использую топорный метод для реализации правила (3) (4), для правила (3) нам просто нужно проверить, имеет ли текущий ФИ точно такой же элемент, что и существующий путь, если да, то заменить его на последний, т.е. непротиворечивость гарантировано, иначе ничего не делается:
def __checkIdentical(self, path):
"""
The key to keep any identical item sets
sharing an identical ordering.
"""
for op in self.__order_frequent_itemsets:
if set(op) == set(path):
return op
return None
вself.__order_frequent_itemsetsЭто массив FI, который уже существует в FPTree. Обработка правила (4) более хлопотна, потому что проверка префикса — задача с высокой вычислительной сложностью, а в исходной статье четко не объясняется конкретное определение префикса, например
и
,бывший
может быть префиксом последнего, а
Его также можно использовать в качестве префикса для последних, и они соответствуют правилам сортировки подсчетом, но результаты сортировки в них совершенно разные. Итак, что я рассматриваю здесь, это
является критерием сегментации, например, для
С точки зрения,
из
оба 4, и
Оба равны 3, но мы не рассматриваем последний слой, потому что все они могут быть конечными узлами. Таким образом, это может быть реализовано следующим образом:
def __adjustPrefix(self, path):
if len(path) < 2:
return path
prefix = []
count_level = self.__fitemsets[path[0]]
for e in path:
if self.__fitemsets[e] == count_level:
prefix.append(e)
else: break
if len(prefix) == 1:
return path
l = len(prefix)
start = -1
merge_path = None
for op in self.__order_frequent_itemsets:
if not start == -1:
break
if set(prefix).issubset(set(op)):
for i, e in enumerate(op):
if e in prefix:
start = i
merge_path = op
break
if not start == -1:
path[:l] = merge_path[start: l]
return path
вself.__fitemsetsсловарь, в котором хранится количество FI. Тогда мы можем обеспечить как согласованность, так и стабильность в процессе построения дерева следующим образом:
op = self.__checkIdentical(itemsets)
if op == None:
orderitemsets = sorted(itemsets,
key=lambda x: itemsets_dict[x],
reverse=True)
orderitemsets = self.__adjustPrefix(orderitemsets)
self.__order_frequent_itemsets.append(orderitemsets)
else:
orderitemsets = op
Наконец, прогон набора данных на рис. 1 может привести структуру FPTree в соответствие с исходной статьей:
Экспериментальный код этой статьи можно скачать в приложении.
в заключении
FPTree — очень мощная структура сжатия информации о транзакциях, и ее идеологический вклад намного превосходит сам FP-рост, но FPTree чрезвычайно чувствителен к порядку, поэтому я надеюсь, что читатели уделят больше внимания в процессе воспроизведения, и для статьи [1, 2] Проблема случайности результатов предоставленного алгоритма из текущего анализа действительно существует, и причины могут быть различными, но если такой метод будет помещен в рамки с открытым исходным кодом, вред будет огромен, так что я надеюсь Актуально специалисты-практики могут предоставить больше предложений по улучшению. В этой статье могут быть и другие неуместные вещи, или я хотел бы попросить читателей быть щедрыми на них, спасибо!
использованная литература
[1] Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM sigmod record, 29(2), 1-12.
Приложение