Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
Этап 1. Сортировка. Заключается в перегруппировке записей в таблице транзакций. Сначала записи сортируются по уникальному ключу покупателя, а затем по времени внутри каждой группы. Этап 2. Отбор кандидатов. В исходном наборе данных произ- водится поиск всех ЧВП. В частности, на этом этапе происходит по- иск всех одноэлементных шаблонов. Этап 3. Трансформация. Производится для ускорения процесса проверки присутствия последовательностей в наборе транзакций покупателей. Трансформация заключается в замене каждой тран- закции списком ЧВП, которые в ней содержатся. При этом если в транзакции отсутствуют частые предметы, то данная транзакция не учитывается. Аналогичным образом не учитываются предметы, не являющиеся частыми, а также последовательности, транзакции которых не содержат ЧВП. Интеллектуальный анализ данных 102 Этап 4. Генерация последовательностей. Из полученных на предыдущих этапах последовательностей строятся более длинные шаблоны последовательностей. Этап 5. Максимизация (опционально). Среди имеющихся по- следовательностей происходит поиск тех, которые не входят в бо- лее длинные последовательности. Все упомянутые алгоритмы реализованы аналогично (различа- ются в деталях реализации этапа 4 и обладают невысокой вычисли- тельной эффективностью). 6.7.2. Алгоритм GSP Для существенного повышения вычислительной эффективности (до 20 раз) сиквенционального анализа предложена модификация алгоритма AprioriAll, названная GSP (англ. Generalized Sequential Pattern, обобщенный сиквенциональный паттерн), учитывающая ограничения по времени между соседними транзакциями [1, 35]. В случае с алгоритмом GSP требуется учитывать дополнитель- ные условия, чтобы определить, содержит ли последовательность указанную последовательность (подпоследовательность). Введем такие параметры, как минимальное и максимальное до- пустимое время между транзакциями (min_gap и max_gap), а также понятие скользящего окна размера win_size. Допускается, что эле- мент последовательности может состоять не из одной, а из несколь- ких транзакций, если разница во времени между ними меньше, чем размер окна. Последовательность d = d1 ... dmсодержит последовательность s = s 1 ... s n , если существуют такие целые числа l1≤ u1 < l2≤ u2 < … < ln ≤ un , что: 1) si содержится в объединении dk, где k = l i ..u i ,1 ≤ i ≤ n; 2) t транзакции (du[i])– t транзакции (dl[i]) ≤ win_size, 1 ≤ i ≤ n; 3) min_gap < t транзакции (dl[i])– t транзакции (du[i – 1]), 2 ≤ i ≤ n; 4) t транзакции (du[i])– t транзакции (dl[i – 1]) ≤ max_gap, 2 ≤ i ≤ n. Выполнение алгоритма GSP предусматривает несколько прохо- дов по исходному набору данных. При первом проходе вычисляется 6. Основные методы анализа и интерпретации данных 103 поддержка для каждого предмета и из них выделяются частые. Каж- дый подобный предмет представляет собой одноэлементную после- довательность. В начале каждого последующего прохода имеется некоторое число ЧВП, выявленных на предыдущем шаге алго- ритма. Из них будут формироваться более длинные последователь- ности-кандидаты. Каждый кандидат представляет собой последовательность, длина которой на один больше чем у последовательностей, из кото- рых кандидат был сформирован. Таким образом, число элементов всех кандидатов одинаково. После формирования кандидатов про- исходит вычисление их поддержки. В конце шага определяется, какие кандидаты являются ЧВП. Найденные ЧВП послужат исход- ными данными для следующего шага алгоритма. Работа алгоритма завершается тогда, когда не найдено ни одной новой ЧВП в конце очередного шага или когда невозможно сформировать новых кан- дидатов. Таким образом, в работе алгоритма можно выделить следующие основные этапы: 1. Генерация кандидатов. 1.1. Объединение. 1.2. Упрощение. 2. Подсчет поддержки кандидатов. Рассмотрим эти операции более подробно. Этап 1. Генерация кандидатов. Пусть Lk содержит все частые k-последовательности, а Ck – множество кандидатов из k-последо- вательностей. В начале каждого шага имеем Lk − 1– набор из (k – 1) ЧВП. На их основе необходимо построить набор всех k ЧВП. Введем понятие смежной подпоследовательности. При наличии последовательности s = s1 s2 ... snи подпоследо- вательности c, c будет являться смежной последовательностью s, если соблюдается одно из условий: – c получается из s при удалении предмета из первого {s1} или последнего {sn} предметного множества; – c получается из s при удалении одного предмета из предмет- ного множества si, если в его составе не менее двух предметов; Интеллектуальный анализ данных 104 – c – смежная подпоследовательность cʹ, где cʹ – смежная под- последовательность s. Например, дана последовательность s = {1,2}, {3,4}, {5}, {6}. Последовательности {2}, {3,4}, {5}, {1,2}, {3}, {5}, {6}и {3}, {5} являются смежными подпоследовательностями s, а последова- тельности {1,2}, {3,4}, {6}и {1}, {5}, {6}таковыми не явля- ются. Если некоторая последовательность содержит последователь- ность s, то она также содержит и все смежные подпоследовательно- сти s. Генерация кандидатов происходит в два этапа (условно назовем эти этапы функцией candidate_gen_SPM()). Этап 1.1. Объединение (англ. join). Создаем последовательно- сти-кандидаты путем объединения двух последовательностей Lk − 1 и Lk − 1. Последовательность s1объединяется с s2, если подпосле- довательность, образующаяся путем удаления первого предмета из s1будет та же, что и в случае удаления последнего предмета из s2. Объединение последовательностей происходит путем добавления к s1соответствующего предмета из последнего предметного множе- ства s2. Причем возможно два варианта: – если последний предмет из s2составлял одноэлементное предметное множество, то при объединении он будет добавлен к s1 как новое предметное множество; – в противном случае он будет включен в последнее предмет- ное множество s1как его элемент. При объединении L1c L1нужно добавить предмет к s2как от- дельное предметное множество, а также в качестве дополнитель- ного предмета в предметное множество последовательности s1. Так, объединение {x} с {y} дадут как (x, y), таки (x), (y). При- чем x и y упорядочены. Этап 1.2. Упрощение (англ. prune).Удаляем последовательно- сти-кандидаты, которые содержат смежные (k – 1)-последователь- ности, чья поддержка меньше минимально допустимой. Этап 2. Подсчет поддержки кандидатов. Сканируя набор после- довательностей, обрабатываем их по очереди. Для тех кандидатов, 6. Основные методы анализа и интерпретации данных 105 которые содержатся в обрабатываемой последовательности, увели- чиваем значение поддержки на единицу. Для уменьшения количе- ства кандидатов, требующих проверки вхождения в обрабатываемые последовательности, а также для увеличения скорости проверки ис- пользуется хэш-дерево [4]. Проиллюстририруем основные этапы работы алгоритма GSP на примере данных в табл. 8–10. Т а б л и ц а 8 Пример таблицы транзакций магазина ID клиента Время транзакции Транзакция 1 1 20 июля 2015 25 июля 2015 30 90 2 2 2 9 июля 2015 14 июля 2015 20 июля 2015 10, 20 30 40, 60, 70 3 25 июля 2015 30, 50, 70 4 4 4 25 июля 2015 29 июля 2015 2 августа 2015 30 40, 70 90 5 12 июля 2015 90 Т а б л и ц а 9 Пример таблицы последовательностей на основе БД транзакций ID клиента Последовательность данных 1 {30} {90} 2 {10, 20} {30} {40, 60, 70} 3 {30, 50, 70} 4 {30} {40, 70} {90} 5 {90} Т а б л и ц а 1 0 Пример итогового набора последовательностей различной длины с заданным уровнем поддержки Виды последовательностей Последовательные паттерны с поддержкой ≥ 25% 1-последовательности {30}, {40}, {70}, {90}, 2-последовательности {30} {40}, {30} {70}, {30} {90}, {40} {70} 3-последовательности {30} {40, 70} Интеллектуальный анализ данных 106 Формальная запись алгоритма GSP может быть представлена следующим образом: Алгоритм GSP(S): Шаг 1. C 1 ← init_pass(S); //первый проход через S Шаг 2. F 1 ← {({ f }) | f C 1 , f.count/n ≥ minsup}; //n – число последовательностей в S Шаг 3. for (k = 2; F k-1 ≠ ; k++) do // формирование подпоследовательностей из S Шаг 4. C k ← candidate_gen_SPM(F k-1 ); // однократное сканирование набора данных Шаг 5. for (для каждой последовательности данных s S) do Шаг 6. for (для каждого кандидата c C k ) do Шаг 7. if c содержится в s then Шаг 8. c.count++; // инкремент счетчика поддержки Шаг 9. end Шаг 10. end Шаг 11. F k ← {c C | c.count / n ≥ minsup} Шаг 12. end Шаг 13. return ∪ k F k ; Детали реализации функции генерирования кандидата-последо- вательности candidate_gen_SPM() изложены выше. Пример генерирования кандидатов-последовательностей приве- ден в табл. 11. Т а б л и ц а 1 1 Пример работы этапа генерирования кандидатов-последовательностей 3-последовательности 4-последовательности После присоединения После упрощения {1, 2} {4} {1, 2} {4, 5} {1, 2} {4, 5} {1, 2} {5} {1, 2} {4} {6} {1} {4, 5} {1, 4} {6} {2} {4, 5} {2} {4} {6} 6. Основные методы анализа и интерпретации данных 107 Недостатками подобных алгоритмов, существенно снижающими вычислительную эффективность обработки данных, являются: – большое количество обращений к базе данных, соответству- ющее длине максимального кандидата-последовательности; – большое число генерируемых кандидатов-последовательно- стей. 6.8. Многоуровневое машинное обучение Для обеспечения устойчивости результатов машинного обуче- ния используются различные методы ансамблирования моделей, основная суть которых заключается в объединении по тем или иным правилам результатов работы семейства моделей («слабых» классификаторов), позволяя в результате получить «сильный» клас- сификатор. Такое ансамблирование должно позволить усовершен- ствовать итоговый результат работы модели, уменьшая дисперсию или смещение ее результатов (рис. 22). Рис. 22. Иллюстрация различной точности результатов модели Низкая дисперсия Высокая дисперсия Вы со ко е см ещ ен ие Ни зк ое с м ещ ени е Интеллектуальный анализ данных 108 Этот раздел посвящен основным подходам к ассамблевым по- строениям моделей машинного обучения, получившим наименова- ния на основе их англоязычных аналогов – бэггинг (англ. bagging), стекинг (англ. stacking) и бустинг (англ. boosting). При этом начать изложение следует с подхода к формированию обучающих данных для ансамблевого обучения, получившего название бутстрэпппинг (англ. bootstrapping). 6.8.1. Бутстрэппинг Применение любого подхода к использованию семейства моде- лей предполагает разделение обучающей выборки так, чтобы каж- дой из моделей досталась достаточная и репрезентативная подвы- борка обучающих данных. Рис. 23. Иллюстрация создания семейства подвыборок методом бутстрэп Популяция Выборка Экспериментальный образец Начальная загрузка Заключение Заключение n = 1 n = 1 n = 2 n = … n = 1000 6. Основные методы анализа и интерпретации данных 109 На практике такое формирование подвыборок для каждой из по- рой многочисленных моделей семейства может быть затруднитель- ным вследствие дефицита обучающих данных (иногда даже для од- ной единственной модели). В этом случае получил распространение метод бутстрэп – практический метод формирования семейства (как правила значительного числа) подвыборок на базе элементов имеющейся выборки с возвратом в нее элементов, получая возмож- ность построения статистик, предельно близких к статистикам ис- ходной выборки (рис. 23). Суть метода бутстрэп заключается в следующем: – для формирования новой «бутстрэп выборки» из исходной выборки X с количеством экземпляров N статистически случайно по методу Монте-Карло (с одинаковой вероятностью 1/N) возьмем N объектов с возвращением объекта обратно в исходную выборку. Причем каждый раз выбор осуществляем из всех исходных N объ- ектов. Из-за возвращения среди них могут оказаться и «повторы»; – обозначим новую «бутстрэп выборку» через X 1 . Повторяя процедуру M раз, сгенерируем M подвыборок X 1 , …, X M ; – при достаточно большом M получим возможность оценивать различные статистики исходного распределения с высокой точностью. 6.8.2. Бэггинг Bagging (от Bootstrap aggregation) – один из самых простых ви- дов ансамблей, в котором обучение базовых моделей производится параллельно. Изначально был придуман для улучшения результа- тов моделей на основе деревьев решений, однако может использо- ваться на любых моделях. Главным преимуществом бэггинга является значительное увели- чение точности предсказания ансамбля относительно их базовых моделей (увеличение может достигать 10–40%), что реализуется за счет уменьшения разброса ответов базовых моделей при усреднении. Отмечают следующие недостатки этого метода: – слабая математическая обоснованность улучшения точности предсказаний; Интеллектуальный анализ данных 110 – недетерминированность результата из-за случайного форми- рования выборок; – относительная сложность интерпретации результатов. Схематически описать принцип бэггинга можно следующим об- разом (рис. 24). Из обучающей выборки методом бутстреппинга формируется m тренировочных выборок T 1 , …, T m . На каждой вы- борке обучаются модели с использованием одинаковых алгорит- мов. Итоговая модель будет усреднять предсказания всех этих ал- горитмов (в случае классификации это будет голосование): P f Рис. 24. Бэггинг В качестве примера широко используемой реализации алго- ритма бэггинга следует рассмотреть случайные леса (random forest, или forest of randomized trees). Алгоритм представляет собой усо- вершенствованный метод бэггинга Лео Бреймана путем использова- ния метода случайных подпространств, предложенного Tin Kam Ho. 𝑇 1 𝑇 2 𝑇 𝑚 … … … С 1 С 2 С 𝑚 𝑃 1 𝑃 2 𝑃 𝑚 Голосование 𝑃 𝑓 Но вы е да нн ы е Бутстрэп выборки Модели классификации Предвычисление Финальное вычисление Обучающая выборка 6. Основные методы анализа и интерпретации данных 111 Основная идея заключается в использовании большого ансамбля решающих деревьев, отдельные результаты которых не дают вы- сокого качества классификации (предсказания). Хороший итого- вый результат получается за счет большого количества деревьев в ансамбле. Метод случайных подпространств позволяет снизить коррелированность между деревьями и избежать переобучения. Базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом. Данные для ансамбля генерируются методом бутстрэппинга. Далее по каждой из подвыборок X n строим решающее дерево b n Дерево строится до полного исчерпания подвыборки. Для задачи классификации выбирается решение голосованием по большинству (каждое дерево относит классифицируемый объект к одному из классов, и побеждает класс, за который проголосовало наибольшее число деревьев), а в задаче регрессии – средним. Таким образом, случайный лес – это бэггинг над решающими деревьями, при обучении которых для каждого разбиения при- знаки выбираются из некоторого случайного подмножества при- знаков. 6.8.3. Стекинг Стекинг (Stacked Generalization, Stacking) – метод ансамблиро- вания моделей, который объединяет несколько моделей классифи- кации или регрессии соответствующим метаалгоритмом. Базовые модели обучаются на тренировочной выборке, а метаалгоритм обу- чается на ответах базовых моделей. Простейшая схема стекинга – блендинг (blending) (рис. 25), когда обучающую выборку делят на две части. На первой части обучаются базовые алгоритмы, а на вто- рой части и на тестовой выборке получаются ответы обученных мо- делей. Ответ каждого базового алгоритма рассматривается как «метапризнак», на таких «метапризнаках» обучается «метаалго- ритм». Полученный алгоритм запускается на «метапризнаках» те- ста и получается финальный ответ. |