Эта статья впервые опубликованаколонна Джижи
Прогнозирование последовательности — одно из самых популярных приложений глубокого обучения на сегодняшний день. От создания систем рекомендаций до распознавания речи и обработки естественного языка прогнозирование последовательности имеет широкий спектр приложений.
Существует множество различных способов реализации прогнозирования последовательности, например, использование марковских моделей/ориентированных графов в машинном обучении, RNN/LSTM в глубоком обучении и т. д. В этой статье мы будем использовать алгоритм под названием «Компактное дерево предсказаний» (CPT). Хотя этот алгоритм известен немногим, он превосходит многие очень известные методы, такие как вышеупомянутые марковские модели и ориентированные графы. Давайте поделимся тем, как использовать CPT для решения проблемы прогнозирования последовательности.
предсказание последовательности
Прогнозирование последовательности используется всякий раз, когда мы хотим предсказать, что за событием может последовать другое конкретное событие. Прогнозирование последовательности может широко использоваться во многих областях, таких как:
- Предварительная загрузка веб-страницы: на основе последовательности веб-страниц, которые посетил пользователь, браузер может предсказать веб-страницу, которую пользователь, скорее всего, посетит следующей, чтобы загрузить веб-страницу заранее, повысить скорость открытия. веб-страницы и оптимизировать взаимодействие с пользователем.
- Рекомендация продукта: в соответствии с последовательностью продуктов, добавленных пользователем в корзину, спрогнозируйте продукты, которые могут заинтересовать пользователя в следующий раз, чтобы рекомендовать продукты для пользователя.
- Прогноз погоды: предскажите погоду на следующий период на основе предыдущих погодных условий. Современные подходы к решению прогнозов последовательности
Наиболее распространенными методами прогнозирования последовательности сегодня являются LSTM и RNN, которые стали популярным выбором для моделирования последовательности, для текста, аудио и многого другого. Однако у них есть две основные проблемы:
- Время обучения очень долгое, часто десятки часов
- Если последовательность содержит элементы, которые не были замечены в предыдущих итерациях обучения, их необходимо переобучить. Этот процесс является дорогостоящим, и в случае частых новых проектов их нельзя использовать.
Познакомьтесь с компактным деревом прогнозов (CPT)
Алгоритм Compact Prediction Tree (CPT) часто более точен, чем традиционные методы машинного обучения, такие как марковские модели, и методы глубокого обучения, такие как автоэнкодеры, при решении задач прогнозирования последовательности.
Большим преимуществом CPT является его быстрое обучение и время прогнозирования. Ранее алгоритм CPT был реализован только в Java-коде, к счастью, он появился позже.версия Python.
Хотя библиотека в настоящее время не очень полная, производительность по-прежнему отличная. Давайте поговорим о внутренних принципах алгоритма CPT и о том, почему он лучше алгоритмов машинного обучения, таких как цепи Маркова и гистограммы.
Понимание структур данных в CPT
Сначала нам нужно понять формат данных, принятый библиотекой Python CPT. CPT принимает два файла .csv — тестовый файл и обучающий файл. Учебный файл содержит обучающие последовательности, тестовый файл также содержит последовательности, и необходимо предсказать следующие 3 элемента для каждой последовательности. Для ясности последовательности в тестовом и обучающем файлах определены следующим образом:
1,2,3,4,5,6,7
5,6,3,6,3,4,5
.
.
.
Обратите внимание, что последовательности могут быть разной длины. Кроме того, последовательности с горячим кодированием не применяются. Алгоритм CPT использует три основные структуры данных, которые мы кратко интерпретируем ниже.
1 Дерево предсказаний
Дерево предсказаний — это дерево, состоящее из узлов, в каждом из которых 3 элемента:
- элемент данных (элемент): фактический элемент данных, хранящийся в узле
- дочерние элементы: список всех дочерних элементов этого узла
- parent: ссылка или ссылка на родителя этого узла
Дерево прогнозов — это, по сути, структура данных trie, которая сжимает все обучающие данные в дерево. Если вы не знаете, как работает структура данных trie, вы можете обратиться к следующим двум диаграммам структуры trie последовательности:
序列1: A, B, C
序列2: A, B, D
Структура данных Trie сначала начинается с первого элемента A последовательности A, B, C, добавляя A к корневому узлу. Затем к А добавляется В, а к В добавляется С. Для каждой новой последовательности trie снова начинается с корневого узла, пропуская, если элемент уже был добавлен в структуру данных.
Окончательная структура данных показана выше. Вот как деревья прогнозов эффективно сжимают обучающие данные.
2 Перевернутый индекс
Инвертированный индекс — это словарь, в котором ключи — это элементы обучающего набора, а значения — набор последовательностей, в которых этот элемент встречается. Например: Последовательность 1: A,B,C,D Последовательность 2: B,C Последовательность 3: A,B Обратный индекс приведенной выше последовательности выглядит следующим образом:
II = {
‘A’:{‘Seq1’,’Seq3’},
’B’:{‘Seq1’,’Seq2’,’Seq3’},
’C’:{‘Seq1’,’Seq2’},
’D’:{‘Seq1’}
}
3 Таблица поиска
Таблица поиска также является словарем, где ключи — это идентификаторы последовательностей, а значения — конечные узлы последовательностей в дереве предсказаний. Например:
序列1: A, B, C
序列2: A, B, D
LT = {
“Seq1” : node(C),
“Seq2” : node(D)
}
Понять, как обучение и прогнозирование работают в CPT
Мы закрепим наше понимание процесса обучения и прогнозирования алгоритма CPT на примере. Вот пример тренировочного набора:
Как видите, приведенный выше тренировочный набор состоит из 3 последовательностей. Мы представляем их с идентификаторами: seq1, seq2 и seq3. A, B, C и D — все отдельные уникальные элементы в наборе обучающих данных.
фаза обучения
На этапе обучения одновременно будут построены дерево прогнозов, инвертированный индекс и таблица поиска. Теперь рассмотрим все этапы тренировочного процесса:
Шаг 1: Вставьте A, B, C
Мы получаем корневой узел и переменную текущего узла, изначально установленную на корневой узел.
Давайте начнем с A и посмотрим, является ли A дочерним элементом корневого узла. Если нет, мы добавляем A в список дочерних узлов корневого узла, добавляем запись для A в инвертированный индекс со значением seq1 и перемещаем текущий узел в A.
Затем мы смотрим на следующий элемент, которым является B, чтобы увидеть, существует ли B как дочерний элемент текущего узла (которым является A). Если нет, добавьте B в подсписок A, добавьте запись для B в инвертированный индекс со значением seq1 и переместите текущий узел в B.
Затем мы повторяем описанный выше процесс, пока не закончим добавление последнего элемента seq1. Наконец, мы добавим последний узел seq1, то есть C, в таблицу поиска с ключом, равным «seq1», и значением, равным узлу C.
Шаг 2: Вставьте A и B
Шаг 3: Вставьте A, B и C
Шаг 4: Вставьте B и C
Мы продолжаем этот процесс, пока не исчерпаем каждую строку в обучающем наборе данных (помните, что каждая строка представляет собой последовательность). Теперь у нас есть все необходимые структуры данных, чтобы начать делать прогнозы на тестовом наборе данных. Давайте посмотрим на процесс предсказания ниже.
этап предсказания
На этапе прогнозирования прогнозы делаются итеративно для каждой последовательности данных в тестовом наборе. Для одной строки мы используем инвертированный индекс, чтобы найти последовательности, похожие на эту строку. Затем мы находим последующие последовательности подобных последовательностей, добавляем элементы из последующей последовательности в словарь подсчета и даем оценку. Наконец, используйте словарь count, чтобы вернуть элемент с наивысшим баллом в качестве окончательного прогнозируемого значения. Мы рассмотрим детали каждого шага для более глубокого понимания CPT.
Целевая последовательность - A, B
Шаг 1: Найдите последовательности, похожие на целевую последовательность.
Используя инвертированный индекс, чтобы найти последовательность, похожую на целевую последовательность, выполните поиск, выполнив следующие шаги:
- найти уникальный элемент целевой последовательности,
- Найдите набор идентификаторов последовательностей, в которых существует конкретный уникальный элемент,
- Затем возьмите пересечение всех наборов уникальных предметов.
Например:
存在A项的序列集= {‘Seq1’,’Seq2’,’Seq3’}
存在B项的序列集= {‘Seq1’,’Seq2’,’Seq3’,’Seq4’}
和目标序列相似的序列=集合A和集合B的交集= {‘Seq1’,’Seq2’,’Seq3’}
Шаг 2: Найдите преемника каждой последовательности, похожей на целевую последовательность.
Для каждой подобной последовательности последующая последовательность определяется как самая длинная подпоследовательность после появления последнего термина в целевой последовательности в аналогичной последовательности за вычетом термина, присутствующего в целевой последовательности.
Мы понимаем лучше на следующем примере:
目标序列=[‘A’,’B’,’C’] 相似序列= [‘X’,’A’,’Y’,’B’,’C’,’E’,’A’,’F’]
目标序列的最后一项=‘C’
相似序列中‘C’最后发生后的最长子序列= [‘E’,’A’,’F’]
后续序列=[‘E’,’F’]
Шаг 3: Добавьте элементы и их оценки в последующей последовательности в словарь подсчета.
Добавляет элемент и оценку последующей последовательности каждой похожей последовательности в словарь. Например, продолжите пример выше. Баллы за все элементы в последующей последовательности ['E','F'] рассчитываются следующим образом:
计数字典的初始状态= {},是一个空字典
如果字典中不存在该项，那么，
分值=1 + （1/相似序列的数量）+（1/计数字典中当前项的数量+1）*0.001
否则，
分值=（1+（1/相似序列的数量）+（1/计算表中当前项的数量）*0.001） * 原来的分值
那么对于元素E，也就是后续序列的第一个项，分值会是：
分值[E]=1 + (1/1) + 1/(0+1)*0.001 = 2.001
分值[F]=1 + (1/1) + 1/(1+1)*0.001 = 2.0005
После приведенных выше вычислений словарь count будет выглядеть так: counttable = {'E' : 2.001, 'F': 2.0005}
Шаг 4. Используйте вычислительный словарь для прогнозирования
Наконец, в качестве предсказанного значения используется ключ с наибольшим значением, возвращаемым в словаре count. В нашем примере выше E возвращается как прогнозируемое значение.
Создавайте модели, делайте прогнозы
Шаг 1: Клонируйте репозиторий GitHub отсюда:
git clone GitHub.com/NE и AJ SAR вау…
Шаг 2. Используйте следующий код, чтобы прочитать CSV-файл, чтобы обучить свою модель и сделать прогнозы.
#导入CPT文件中的全部内容
from CPT import *
#创建CPT类的一个对象
model = CPT()
#读取训练和测试文件，将其转换为数据和目标
data, target = model.load_files(“./data/train.csv”,”./data/test.csv”)
#训练模型
model.train(data)
#用测试数据集做出预测
predictions = model.predict(data,target,5,1)
Эпилог
В этой статье мы обсуждаем эффективный и точный алгоритм, который можно использовать для решения задач прогнозирования последовательности, компактное дерево прогнозирования (CPT). Вы можете сами найти некоторые наборы данных и попробовать этот алгоритм самостоятельно.
Использованная литература:www.analyticsvidhya.com
0806 «Искусственный интеллект — от нуля до мастера» со скидкой, ограниченной по времени!
Нажмите здесь, чтобы узнать подробности
Болтать и смеяться Онлайн-программирование Узнать об этом?
(Первые 25 студентов также могут получить купон на 200 иен)