Диссертация. Основам искусственного интеллекта и анализа данных в курсе информатики на уровне среднего общего образования Научная
 Скачать 4.76 Mb.
|
|
SETM, 131 похожий по принципу, но использующий некоторые особенности языка SQL. Но оба алгоритма на каждом шаге генерировали всё новые данные и постоянно обращались к старым. Тогда один из авторов, Ракеш Агравал, решил усовершенствовать алгоритм AIS, сделав его масштабируемым [168]. Идея делает алгоритм Apriori настолько популярным, что он до сих пор является одним из пятёрки лидеров (топ) алгоритмов Data Mining. Более того зачастую название этого алгоритма отождествляют совсем анализом потребительских корзин В основе этого алгоритма лежит очевидный для многих факт если набор из трех покупок встречается пять раз, то набор их двух любых покупок этого набора встречается не менее пяти раз [45, Глава 4]. Используя алгоритм Apriori (от лат. a priori – до опыта, независимо от опыта, можем искать часто встречающиеся типовые наборы, автоматически отбрасывая те покупки, которые встречаются редко. Сего работой обучающиеся сталкиваются ежедневно, делая покупки в магазине и выбирая товары с полок. Задача поиска шаблонов покупок, совершаемых клиентами супермаркетов, актуальна сегодня и, вероятно, останется такой ив будущем. Все крупные торговые сети активно собирают данные о своих клиентах и стараются идентифицировать постоянных покупателей, например, с помощью скидочных карт, выдаваемых в обмен на заполненные анкеты. Простыми понятным примером является расположение полок в гипермаркете: сливки лежат рядом с кофе и т. д. Здесь работает следующее правило если (if) человек купил кофе, тогда (then) он захочет добавить в него сливки. Нахождение определённых правил, которые встречаются достаточно редко, позволяет продать потребителю тот товар, на который он не обратил бы внимания, если бы нерасположение на витрине, а также 132 предсказать сезонный спрос на какой-либо товар. Именно алгоритм Apriori применяется при составлении акций и распродажи позволяет получить больший доход, сократив убытки от занятых складов и полок. Аналогично его можно использовать для анализа продуктивности взаимодействия людей и составления эффективных команд (в менеджменте. Алгоритм Apriori также входит в состав медицинских диагностических экспертных систем [191]. Apriori предназначен для выявления ассоциативных правил при исследовании больших объёмов информации. Главная его особенность состоит в том, что он масштабируемый, те. экономный по отношению к памяти и, следовательно, времени выполнения, что крайне важно для объёмов, исчисляемых гигабайтами или терабайтами информации. Масштабированным алгоритм становится из-за использования свойства антимонотонности, которое служит для снижения пространства поиска подходящих элементов. Его работу можно разделить на два больших блока. Свободный поиск • формирование кандидатов (candidate generation) – поиск подходящих групп кандидатов • подсчёт кандидатов (candidate counting) – проверка кандидатов k- того шага на встречаемость и преодоление порога минимальной поддержки. Смысловой поиск • составление ассоциативных правил • проверка их достоверности. Формирование и проверка кандидатов работает до достижения негативной области (negative border) – формирования наборов кандидатов, все элементы которого являются часто встречающимися, асам набор – нет [117]. 133 Затем происходит проверка исследователем и подготовка отчёта. Эксперт оценивает результаты последующему принципу (см. Таблицу 7) [45]: Таблица 7. Практическое значение достоверности % Достоверность 5–10 Важная ниша для проведения акций. Означает, что большинство не интересуется товарами, которые рассматривались, вместе, но есть постоянные покупатели, которые выбирают данную пару (или больше) товаров. Возможно привлечение новых постоянных покупателей. >60 Достоверный факт, на него можно положиться. 100 Была маленькая выборка или правило − неоспоримая истина. Для каждого часто встречающегося множества можно составить как минимум два правила. Для нахождения достоверности необходимо разделить значение поддержки всего множества назначение поддержки элемента посылки. Например, для множества чай, сахар можно вывести те, кто пьют чай, добавляют сахар ( ); те, кто любит сахар, добавляют его в чай ( ). Значение 100% при работе с большими данными обычно сигнализирует об ошибке, однако часто встречается на учебных выборках. Вы с ним столкнётесь только в первых упражнениях. Для работы алгоритма необходимо привести данные к бинарному виду и определённой структуре. Для этого общую таблицу приводят к нормализованному виду. Алгоритм является поуровневым и использующим стратегию поискав ширину и снизу-вверх, поэтому так важно упорядочить таблицу исходных данных. 134 Первоначальный вид таблицы (см. Таблицу 8) приведён далее. Таблица 8. Неупорядоченная таблица покупок Номер чека Наименование товара Количество товара 102 Лосось 3 102 Икра красная 1 103 Лосось 2 103 Хлеб 3 Видно, что в каждом чеке может содержаться более одного товара. Количество товаров для простой реализации алгоритма неважно. После преобразования таблица будет иметь следующий вид (см. Таблицу 9). Таблица 9 Преобразованная таблица покупок Номер чека Лосось Икра красная Хлеб ... 102 1 1 0 103 1 0 1 Каждая строка соответствует отдельной транзакции. Наличие товара отмечается 1 в случае присутствия в корзине, 0 − если товар отсутствует. Количество столбцов в таблице равно количеству различных товаров. Нормализованная таблица имеет уникальные строки и уникальные столбцы. Рассмотрим первый блок. Самый простой вариант решения данной задачи — это перебор всех возможных элементов, что займёт O(2 Items ) операций. Используется свойство антимонотонности: Любой k- 135 элементный набор будет часто встречающимся, если все его (k – 1)- элементные подмножества будут часто встречающимися. Звучит довольно запутано Это значит, что набор из четырёх элементов будет часто встречающимся, если любые три элемента из этого набора будут часто встречающимися. Эти трёхэлементные наборы будут часто встречающимися, только если любые два элемента будут часто встречающимися, а те, в свою очередь, обязаны состоять из часто встречающихся одноэлементных подмножеств. Это и есть реализация стратегии поискав ширину и по направлению снизу-вверх. Если приведённое условие не выполняется (достигается негативная зона, это множество отбрасывается, те. удаляется из памяти, что позволяет алгоритму занимать не слишком много ресурсов и эффективно справляться с большими объёмами данных. Рис. 19. Работа масштабируемого алгоритма APriori На вход подаётся множество всех транзакций и минимальное допустимое значение поддержки ϵ. Поддержка (support) − это сумма элементов столбцов нормализованной матрицы для данной транзакции A,D А C D A,B A,C B,C B,D C,D A,C,D A,B,D A,B,C B,C,D A,B,C,D 136 Для первого прохода поддержка товара считается как где X − номер столбца, те товара, аналогично для Y. Минимальная поддержка задаётся в условиях задачи и является пороговым значением, превышение которого означает, что элементное множество является часто встречающимся. Для учебных задаче значение обычно делают равным 3. Поддержка меньше 3 означает, что товар (или набор товаров) даже три раза не купили. Как было видно из схемы (см. Рис. 19 ) , кандидаты (элементные множества, которые, возможно, станут часто встречающимися, если их поддержка больше или равна минимальной) формируются как всевозможные сочетания из (k – элементных часто встречающихся подмножеств. Когда достигнута негативная зона, необходимо перейти ко второму этапу алгоритма − составлению ассоциативных правил. Для этого выписывают все часто встречающиеся множества. Из каждого множества {a, b} можно получить два правила a→b или же b→a, причём полученные правила могут иметь разную достоверность conf(𝐴 𝑖 ) = sup(𝑋 → Y) sup(X) , где A i − это правило. Затем происходит анализ полученных правил сточки зрения целей применения алгоритма. Тема: РЕГРЕССИЯ. ЛИНЕЙНАЯ РЕГРЕССИЯ. Рассмотрим подробнее задачу регрессии. 137 Регрессия – это выявление зависимости между двумя или более свойствами объектов [35]. Иначе можно сказать, что с помощью регрессии изучают влияние одних свойств на другие. Мы будем рассматривать линейную регрессию, при которой идет поиск зависимости между двумя свойствами, одно из которых независимое, а второе — зависимое. Как ясно из названия, график такой зависимости можно представить в виде прямой линии. В качестве объектов обычно выступают состояния изучаемой сущности в разные отрезки времени [21]. В программировании для снятия такого среза часто используется вызов объекта как current — в его текущем состоянии с сохранением в новую переменную, что равно созданию нового объекта. В физике для тех же целей мы используем переменную Δ. Функции зависимостей между свойствами непрерывны. Зависимость описывают максимально похожей функцией выбранного исследователем порядка. График этой функции должен проходить через максимальное количество изучаемых точек (для линейной регрессии — наших объектов с двумя описанными свойствами. Регрессия отличается от классификации тем, что классификация работает непосредственно с дискретными значениями, то есть напрямую со значениями свойств объектов, а нес отношениями между ними. Разница между настоящей функцией, описывающей линию проходящую через все точки, и функцией, иллюстрирующей общую тенденцию (которую мы ищем, описывается специальной функцией потерь или стоимости (loss/cost function). Качество решения задачи регрессии проверяется обычно через ширину области вокруг графика функции регрессии, в которую попадают объекты. Чем больше такая область – тем хуже мы подобрали зависимость. При решении практического задания мы познакомимся стремя коэффициентами, описывающими качество регрессии Пирсона (r), детерминации и теста Фишера. 138 Методы, решающие задачу регрессии, относятся к прогнозирующим, но также являются описательными (если мы выявляем зависимости только в существующей выборке, то также восполняем пробелы в наших знаниях. Часто методы регрессии производят дистилляцию шаблонов существующие данные заменяются функцией, коэффициенты которой подбираются при работе с обучающей выборкой. В этом случае регрессия изучает независимости между объектами или группами объектов имеющими общее математическое описание, а между...зависимостями. Такой случай возможен в целом, ноне встречается при рассмотрении линейной регрессии. Обучающиеся уже сталкивались с решением задач с помощью регрессионного анализа, когда искали линию тренда при построении графиков в табличных процессорах, а также при использовании сервиса Регрессия в Microsoft Excel, где вручную настраивали входные данные, выбирая только нужные столбцы таблицы. Алгоритмы регрессии применяют, когда необходимо работать с непрерывными данными и выявлением зависимостей между ними нужно восстановить пропущенные значения (такая задача по- другому называется задачей интерполяции необходимо узнать ожидаемое значение в будущем на основе текущих данных — найти значения переменной вне известного интервала задача экстраполяции требуется выявить характеристику изменения, а не найти конкретные значения переменных. Как же при регрессии реализуется обучение с учителем 10 Под дистилляцией шаблонов понимают набор функций, производящих упорядочивание полученных машиной закономерностей в знания, понятные для пользователя-человека, то есть интерпретируемые исследователем. 139 Во-первых, данные подаются в формализованном виде. Обычно используют запись в формате готовой матрицы значений (то есть, таблицы) или же n переменных вида, где 1 i n, а каждый объект описывается k свойствами. В случае с линейной регрессией объект имеет всего два свойства (k=2), причём мы планируем выяснить отношение между ними. Для этого одно из свойств выбирается как независимое , а второе рассматривается как зависимое , то есть в привычном нам виде Во-вторых, сам процесс обучения заключается в подборе таких коэффициентов уравнения регрессии, при которых значение ошибки для выборки минимально. При рассмотрении линейной регрессии мы стараемся подобрать коэффициенты для уравнения знакомого из алгебры вида , где коэффициенты . Мы его немного видоизменим для лучшего понимания позднее. Линейная регрессия — самый распространённый и простой регрессионный метод. Она строится наследующих предположениях [167]: линейности – зависимость описывается прямой нормальности остатков – нормальное распределение предсказанных и наблюдаемых значений (при визуализации проверяется с помощью построения гистограммы. При линейной регрессии рассматривается следующая зависимость : В приведённой формуле – это те самые коэффициенты регрессии, которые требуется подобрать для каждого объекта . Мы 140 специально заменим здесь на и введём x 0 = 1, чтобы показать линейный вид функции. Перепишем в более удобном виде, понимая, что идеальное описание зависимости — это тов котором фигурируют только коэффициенты при , а именно . Остаётся ещё погрешность в виде таинственного , которую мы назовём : Итак – функция, описывающая все зависимые переменные ; – независимые переменные – коэффициенты, которые находятся вовремя обучения – погрешность, она же остаток. Остаток – это отклонение конкретного наблюдения от линии прогнозирования. Он бывает как положительный (прямая связь с независимой переменной/переменными), таки отрицательный (обратная связь. Для каждой пары (x i , y i ) остаток – собственный. Рассмотрим график на Рис. 20. 141 Рис. 20. Пример графика с линией тренда Те объекты (точки, у которых остаток положительный, находятся над линией тренда. Точки с отрицательным остатком расположены ниже линии тренда, причём расстояние, на которое они отдаляются от линии, различается. Идеальная функция , которая бы описала зависимость объектов, изображённых на рисунке, является , что, как видите, является квадратичной функцией. Так как мы подбираем похожую линейную функцию, остатки неизбежны. И именно по их размеру и характеру мы сможем понять, насколько хороша подобранная нами линейная функция, которую мы объяснили формулой, учитывающей . Напомним, что в исходном описании объектов мы имеем только два свойства , причём второе выражаем как функцию . Иначе говоря, мы можем записать ; Коэффициенты при обучении можно задавать разными способами, включая подбор наугад. И всё-таки возможны случаи, когда слишком 142 высокие и слишком низкие коэффициенты взаимно гасят друг друга. Чтобы этого избежать, проверяют сумму квадратов ошибок, которую хотят минимизировать. Отсюда появился термин минимизации квадратов отклонений RSS (Residual Sum of Squares). Отметим, что она является одной из функций потерь или стоимости (loss/cost function). Чаще всего это делается с помощью метода наименьших квадратов (МНК) [20]. Когда находятся такие коэффициенты, что их сумма квадратов минимальна, их выбирают как оптимальные 𝑅𝑆𝑆 = идеальная) − 𝜑 объяснённая (𝑥 𝑖 )) 2 → 𝑚𝑖𝑛; 𝑛 𝑖=1 𝑅𝑆𝑆 = ∑ ε 𝑖 2 → Также нам при расчётах понадобится ещё две суммы. Во-первых, общая сумма квадратов TSS (total sum of squares): 𝑇𝑆𝑆 = идеальная) ) 2 𝑛 𝑖=1 Во-вторых, мы будем рассматривать, как вы уже догадались, объяснённую сумму квадратов ESS (explained sum of squares): 𝐸𝑆𝑆 = ∑(𝜑 объяснённая (𝑥 𝑖 ) ) 2 𝑛 𝑖=1 Причём имеет место факт, что 𝑇𝑆𝑆 = 𝑅𝑆𝑆 + Для проверки качества полученной регрессионной прямой высчитывается коэффициент детерминации R 2 . Он определяет, насколько построенная модель регрессии (выраженная функцией ) описывает всю изменчивость исходных данных ( ). Мера определённости принимает значения в пределах [0; 1], причём близость к 1 143 означает отличный результата близость к 0 — данные были случайны. Для точности чаще изучаются именно квадраты сумм, которые мы описали ранее 𝑅 2 = 𝐸𝑆𝑆 TSS , 𝑅 2 ∈ [0; а также 𝑅 2 = 1 Коэффициент, который называется R 2 , мы, как правило, используем без квадрата и обозначаем r. Такой коэффициент тоже используется для проверки качества регрессии, ион называется коэффициентом корреляции Пирсона. Он измеряется в пределах [-1;1] и позволяет определить, насколько пропорциональна изменчивость двух (строго двух) переменных. Такая зависимость одного параметра от другого называется корреляцией. При коэффициенте 0 зависимость отсутствует, при 1 — полная прямая зависимость, при -1 — полная обратная зависимость переменных. На графике мы будем это видеть, как положительное или отрицательное отклонение от линии графика регрессии. Этот коэффициент рассматривается для линейных зависимостей, потому и может быть применён при работе с линейной регрессией, однако ограничением является нормальное распределение наших объектов. Коэффициент Пирсона находится последующей формуле 𝑟 идеальная) ∙ идеальная) 𝑛 𝑖=0 √𝑇𝑆𝑆 ∙ Этот коэффициент проверяет такой параметр, как теснота — насколько близко объекты расположены к полученной прямой. Следует отметить, что коэффициент Пирсона менее устойчив к вбросам, чем коэффициент детерминации, поэтому его используют чуть реже. 144 Последний коэффициент проверки качества регрессии, который мы рассмотрим, это тест Фишера. Иногда его также называют мерой. Он показывает значимость рассматриваемой зависимости. Значимостью мы называем вероятность того, что данные наши все-таки случайно оказались зависимы (понятно, что чем больше у нас данных – тем меньше такая вероятность) Для его подсчёта необходимо знать число независимых коэффициентов и число степеней свободы данных . В случае с линейной регрессией , поскольку у нас из двух коэффициентов только один независим. Отсюда следует, что , где n — количество рассматриваемых объектов. Для проверки критерия Фишера необходимо выполнить следующие шаги 1) выдвинуть нулевую гипотезу о том, что зависимость статистически незначима с уровнем значимости ; 2) подсчитать фактическое значение , что для линейной регрессии выглядит как ; 3) сравнить найденное с табличным значением для заданного уровня . В таблицы занесено максимальное возможное значение критерия под влиянием случайных факторов. Если , то зависимость не значима и гипотеза подтверждена. В противном же случае зависимость признают значимой с точностью . |