Пояснительная записка к курсовой работе: 22 страницы, 4 рисунка, 9 источников, 5 приложений

Скачать 101.46 Kb.

Название	Пояснительная записка к курсовой работе: 22 страницы, 4 рисунка, 9 источников, 5 приложений
Дата публикации	03.09.2013
Размер	101.46 Kb.
Тип	Задача

100-bal.ru > Астрономия > Задача

РЕФЕРАТ

Пояснительная записка к курсовой работе: 22 страницы, 4 рисунка, 9 источников, 5 приложений.

Тема работы: Применение метода бритва Оккама в задачах машинного обучения.

Цель работы: Исследования способов применения метода бритвы Оккама в задачах машинного обучения.

Для реализации полученной задачи был реализован набор алгоритмов, основанных на методе бритва Оккама. Путем экспериментальных исследований было произведено сравнение различных алгоритмов.

Алгоритмы были реализованы в виде программ на языке программирования Java.

МАШИННОЕ ОБУЧЕНИЕ, БРИТВА ОККАМА, ИНДУКТИВНОЕ ПРЕДПОЧТЕНИЕ, ID3, LEAST-VALUES, MOST-VALUES, ВЫИГРЫШ ИНФОРМАЦИИ, ДЕРЕВО РЕШЕНИЙ, БАЙЕСОВСКОЕ ОБУЧЕНИЕ, КЛАССИФИКАТОР.
Содержание
Введение

Интерпретации метода «Бритва Оккама»
Применение метода «Бритва Оккама» при построении деревьев решений
Применение метода «Бритва Оккама» в задачах Байесовского обучения.
Программная реализация. Результаты

Выводы

Список использованных материалов

Приложение А

Приложение В

Приложение С

Приложение D

Приложение Е

ВВедение
Pluralitas non est ponenda sine necessitas

Сложность не должна использоваться без необходимости
Так сказал Вильям Оккам в 14 веке. Как известно метод «Бритва Оккама» был обычным в средневековье и не был придуман Оккамом, но из-за частого применения этим человеком получил такое имя. Этот метод говорит нам, что все должно быть проще. Но что именно понимать под «простотой», как выбрать что-то более простое и зачем? По сути «Бритва Оккама» имеет несколько различных интерпретаций, которые описаны ниже. А чтобы продемонстрировать применение этого метода приведем пример.
Существует выборка примеров, принадлежащим двум классам. Каждый из них имеет по два атрибута, и графическое представление этого набора представлено в Приложении А.
Какой из этих троих классификаторов будет наиболее лучшим для данной выборки? А – прямая линия, самый простой классификатор, но он дает слишком большую погрешность. С – сверхточный классификатор, идеально классифицирует данные, но не похоже, что он выделяет какое-то общее распределение примеров, скорее всего он подогнан к выборке и не будет давать правильные результаты на новых примерах. В не такой простой как А и не так хорошо соответствует выборке как С, но он скорее всего будет правильнее классифицировать новые примеры. Таким образом, мы видим, что простота – важный фактор при выборе правил принятия решений.
Метод «Бритва Оккама» достаточно широко используется в машинном обучении. Наиболее часто и полно он используется в задачах построения деревьев, а, кроме того, применяется в Байесовском обучении. Далее мы более подробно рассмотрим различные интерпретации и практическое применение этого древнего метода.

Интерпретации метода «Бритва Оккама»
Принципы, которые лежат в основе этого метода интерпретируются по-разному. Здесь мы представим основные из них и подчеркнем различия. В конце мы опишем два основополагающих принципа, которые содержатся во всех интерпретациях.

Между двумя моделями, которые дают эквивалентные предсказания, следует выбрать более простую.

Эта интерпретация позволяет выбрать основную модель, если более одной дают нужные нам результаты.
Идея интерпретации может быть показана на историческом примере. Галилей показал, что гравитация притягивает предметы вниз с постоянным ускорением. Кеплер независимо открыл, что планеты движутся по почти эллиптическим орбитам вокруг солнца. Позже Ньютон показал, что оба эти закона могут быть выведены как следствия из его универсального закона гравитации. И когда это произошло, стало предпочтительнее использовать унифицированную теорию Ньютона, чем комбинацию законов Галилея и Кеплера. Причины этого предпочтения исходят из первой интерпретации: лучше использовать одну модель, объясняющую оба наблюдения, чем отдельную модель для каждого явления. (По сути, теория Ньютона более соответствует астрономическим данным, чем Кеплера, но мы бы все равно использовали ее, даже если бы они давали только эквивалентные результаты.)

Если два правила принятия решений классифицируют существующие данные одинаково хорошо, то более простое, скорее всего, будет классифицировать новые данные корректнее.

Если дано простое правило принятия решений А и намного более сложное правило В, которое только немного лучше классифицирует существующие данные, то А, скорее всего, будет лучше классифицировать новые данные.

Обе эти интерпретации на самом деле просто частные случаи более примитивного утверждения, которое говорит нам, что, оценивая вероятность будущей правильности классификаторов, следует исходить не только из их производительности на существующей выборке, но и из относительной простоты. Другими словами:

Простые классификаторы, скорее всего, точнее.

Рассмотрим пример трех классификаторов описанных выше. В обычных обстоятельствах мы предпочтем простую квадратичную линию В более комплексной кривой С, потому что В похоже будет классифицировать новые данные лучше, чем С. Это следует из того, что более гладкая форма В отражает какие-то верные свойства данных, а С зависит от случайного шума на выборке.
Два основополагающих принципа.

Предпочтение отдается простейшей модели, объясняющей наблюдения.

То есть предпочтение модели Ньютона двум моделям Галилея и Кеплера. Мы будем говорить об этом принципе, как о свойстве «Бритвы Оккама», потому что он наиболее близок к тому, что сформулировал и применил Вильям Оккам.

Простые классификаторы, скорее всего, точнее.

При прочих равных мы выбираем простой классификатор вместо сложного. Мы даже выберем В, не смотря на то, что он классифицирует данные чуть хуже, чем С. Мы будем называть этот принцип Правилом Простоты.
Все стандартные интерпретации метода «Бритва Оккама» следуют из этих двух основных принципов, продемонстрированных в примерах выше. В нашей работе будет использован второй из них, руководствуясь которым, мы будем выбирать наилучший классификатор.
Применение метода «Бритва Оккама» при построении деревьев решений
Важная техника в машинном обучении, деревья решений, в значительной степени используются в data mining. Они позволяют построить легко понятную человеку модель основополагающих отношений в наборе данных. Могут использоваться для классификации и предсказания.
Метод «Бритва Оккама» нашел широкое применение в построении деревьев решений. Теперь этот метод можно интерпретировать как: самое маленькое дерево, правильно классифицирующее выборку – лучшее. В этом случае размер конечного дерева является для нас индуктивным предпочтением, то есть тем критерием, по которому мы будем определять лучшее из деревьев.
Самое маленькое дерево можно построить полным перебором всех возможных значений, но эта задача может оказаться неразрешимой за конечный промежуток времени на больших выборках. Поэтому, вместо того, чтобы найти наименьшее дерево, мы построим несколько как можно меньших и, воспользовавшись методом «Бритва Оккама», выберем из них лучшее.
Алгоритм построения деревьев решения – жадный алгоритм. Он состоит в построении сверху-вниз, рекурсивно выбирая «лучший» атрибут для текущего узла в дереве. Когда для текущего узла атрибут выбран, создать подузлы для каждого из возможных значений этого атрибута. Далее следует разделить выборку на подвыборки, используя возможные значения атрибута, и назначить их каждому из подузлов соответственно. Повторить действие, пока все примеры не будут однозначно классифицированы.
Алгоритм в псевдокоде:
function decision-tree-learning(examples, attributes, default)

;; examples is a list of training examples

;; attributes is a list of candidate attributes for the

;; current node

;; default is the default value for a leaf node if there

;; are no examples left

if empty(examples) then return(default)

if same-classification(examples) then return(class(examples))

if empty(attributes) then return(majority-classification(examples))

best = choose-attribute(attributes, examples)

tree = new node with attribute best

foreach value v of attribute best do

v-examples = subset of examples with attribute best = v

subtree = decision-tree-learning(v-examples, attributes - best,

majority-classification(examples))

add a branch from tree to subtree with arc labeled v

return(tree)
Выбор лучшего атрибута можно осуществлять различными способами:

Случайно
Least-Values: выбор атрибута с наименьшим количеством значений
Most-Values: выбор атрибута с наибольшим количеством значений
Max-Gain: выбор атрибута с наибольшим значением выигрыша информации

В этой работе программно реализованы последние три способа. Результаты представлены ниже.
Кроме выбора наименьшего метод «Бритва Оккама» имеет еще одно важное применение в алгоритмах построение деревьев решения – уменьшение шума, то есть излишней подгонки деревьев под данные, что позволяет лучше классифицировать новые примеры.
Применение метода «Бритва Оккама» в задачах Байесовского обучения
Метод бритвы Оккама применяется также и в Байесовском обучении. Теория Байеса обеспечивает вероятностный подход к выбору гипотезы в процессе обучения.
Теория Байеса основана на предположении, что атрибуты имеют собственное распределение вероятности и что оптимальное решение принимается из расчета использования этих априорных распределений и наблюдаемых данных.
Теорема Байеса:

P(h) = априорная вероятность гипотезы h

P(D) = априорная вероятность обучающей выборки D

P(h | D) = вероятность того, что гипотеза h – правильная при заданном наборе данных D

P(D | h) = вероятностьD при заданной гипотезе h
Выбираем наиболее вероятную гипотезу при заданных данных:

(максимально апостериорная гипотеза)
Если гипотезы равновероятны (

)

(максимально вероятная гипотеза)

длина описания гипотезы

при оптимальном кодировании гипотез

Программная реализация. Результаты
В ходе этой работы были программно реализованы следующие способы построения деревьев:

Least-Values
Most-Values
Max-Gain

Все они оценивались с точки зрения величины конечного дерева, то есть количества узлов в них.
Для того чтобы получить итоговое дерево, нужно сначала загрузить выборку, потом выбрать ключевой атрибут и нажать на кнопку, соответствующую желаемому способу. Для обучающей выборки, приведенной в Приложении В, получены следующие результаты:

Least-Values 21 узел
Most-Values 17 узлов
Max-Gain 8 узлов

Сами деревья представлены на копиях экрана в Приложениях C, D и Е

Выводы
Наиболее широкое применение метод «Бритва Оккама» получил в построении деревьев решений. При помощи него можно найти оптимальное по своей сложности и величине дерево. Кроме того, этот метод позволяет избежать излишней подгонки данных к обучающей выборке, а значит, позволяет построенным деревьям лучше классифицировать новые примеры. В разработанной программе используются три основных способа построения деревьев решений. Следуя принципу «Бритвы Оккама», самое лучшее дерево построено при помощи алгоритма ID3 (Max-Gain), следующее по размеру дерево было построено, используя Most-Values алгоритм. Самым большим деревом оказалось дерево, построенное при помощи способа Least-values. Таким образом, ID3 – наиболее приближенная к идеальной модель.
Список использованных материалов

Wettschereck, D. and Dietterich, T. G. (1994), Locally Adaptive Nearest Neighbor Algorithms, Advances in Neural Information Processing Systems, 6:184-191. San Mateo, CA: Morgan Kaufmann
Salzberg, S. (1997), On Comparing Classifiers: Pitfalls to Avoid and а Recommended Approach, Data Mining and Knowledge Discovery.
Kaelbling, L. P., Littleman, M. L., Moore, Reinforcement Learning: А Survey. Journal of Artificial Intelligence Research 4
Koenig, S. and Smirnov, Y. (1996), Graph Learning with а Nearest Neighbor Approach, in: Proceedings of the Ninth Annual Conference on Computational Learning Theory COLT'96
Pedro Domingos “Occam’s two razors: the sharp and the blunt”
Pedro Domingos “The role of Occam's razor in knowledge discovery”
William H. Jefferys, James O. Berger “Sharpening Ockham’s razor on a Bayesian strop”
Patrick M. Murphy, Michael J. Pazzani “Exploring the decision forest: an empirical investigation of Occam’s razor in decision tree induction”
Конспект лекций по курсу "Машинное обучение".
Приложение А

Графическое представление выборки примеров.

Приложение В
Выборка PlayTennis.

Пример	Outlook	Temperature	Humidity	Wind	PlayTennis
1 2 3 4 5 6 7 8 9 10 11 12 13 14	Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain	Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild	High High High High Normal Normal Normal High Normal Normal Normal High Normal High	Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong	No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No

Приложение С
Дерево, построенное при помощи Least-Values. Количество узлов – 21.

Приложение D
Дерево, построенное при помощи Most-Values. Количество узлов – 17.

Приложение Е
Дерево, построенное при помощи ID3 (Max-Gain). Количество узлов – 8.

Добавить документ в свой блог или на сайт

	Реферат Пояснительная записка: с., рис., табл., приложений, источников.... Пояснительная записка: с., рис., табл., приложений, источников		Пояснительная записка к курсовой работе по дисциплине «Разработка... Курсовой проект содержит: страниц –22, источников – 5, рисунков – 6, таблиц – 2
	Пояснительная записка к курсовой работе по дисциплине «Разработка... Курсовой проект содержит: страниц –20, источников – 5, рисунков – 6, таблиц – 2		Пояснительная записка к курсовой работе по дисциплине «Разработка... Курсовая работа содержит: страниц – 20, источников – 8, рисунков – 7, таблиц – 2
	Отчет о проведенных работах по очистке данных Отчет 24 страницы без учета приложений, 2 таблицы, 4 рисунка, 1 приложение (в электронном виде в отдельных файлах)		Пояснительная записка к курсовой работе на тему: “Цифровой диктофон” ...
	Пояснительная записка к курсовой работе по дисциплине «Методика профессионального обучения» Бланк задание Вы получаете у преподавателя. Образец бланка задания представлен в приложении методических указаний к выполнению курсовой...		Пояснительная записка к курсовому проекту по дисциплине «Разработка... Курсовой проект содержит: страниц – 22, источников – 8, рисунков – 9, таблиц – 1
	Сибирский государственный технологический университет Курсовой проект содержит расчётно-пояснительную записку из 38 страниц печатного текста, 8 таблиц, 1 рисунка, 7 литературных источников...		Пояснительная записка к курсовой работе по дисциплине «Разработка...
	Пояснительная записка к курсовой работе по дисциплине «Криминалистика» Челябинск: фгбо впо «ЮУрГУ» (ниу), ю-425, 2011, 34 с., библиографический список 39 наим		Пояснительная записка к курсовому проекту по дисциплине «Разработка... Курсовой проект содержит: страниц –19, источников – 5, рисунков – 6, таблиц – 2
	Пояснительная записка к курсовой работе по дисциплине «Уголовное право. Общая часть» Челябинск: фгбо впо «ЮУрГУ» (ниу), ю-425, 2011, 34 с., библиографический список 39 наим		Пояснительная записка к курсовой работе на тему Гитарный симулятор... Объектом исследования является популярная мобильная платформа Android, и ее использование для разработки игр
	Пояснительная записка курсовой работы «Решение задачи о загрузке... Пояснительная записка курсовой работы «Решение задачи о загрузке (задача о рюкзаке), использую рекуррентные соотношения» содержит...		Реферат в работе изложены теоретические вопросы, проведен анализ... Работа содержит 69 страниц, 15 рисунков, 11 таблиц, 18 приложений, 48 источников

Пояснительная записка к курсовой работе: 22 страницы, 4 рисунка, 9 источников, 5 приложений

РЕФЕРАТ

Похожие: