Студопедия

КАТЕГОРИИ:



Мы поможем в написании ваших работ!

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Мы поможем в написании ваших работ!

Эвристика выбора свойств на основе теории информации


Каждое свойство можно рассматривать с точки зрения его вклада в процесс классификации. Например, если необходимо определить виды животных, то одним из признаков классификации является откладывание яиц. Алгоритм при выборе корня текущего дерева оценивает удельный вес информации, добавляемой каждым свойством. Затем он выбирает свойство, имеющее наибольшую информативность. Теория информации обеспечивает математическую основу для измерения информативности сообщения. Каждое сообщение можно рассматривать как экземпляр в пространстве возможных сообщений. Передача сообщения соответствует выбору одного из возможных сообщений. С этой точки зрения целесообразно определить информативную емкость сообщения в зависимости от размера пространства и частоты использования каждого возможного сообщения.

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

Предположим, что существует монета, при подбрасывании которой в трех из четырех случаях выпадает решка. Если знать, что вероятность выпадения решки составляет 3/4, то в 3/4 случаев можно правильно угадать результат игры.

Шеннон формализовал эти наблюдения, определив количество информации в сообщении как функцию от вероятности р передачи каждого возможного сообщения, а именно- log2 p. Имея пространство сообщений М={m1, m2 …..mn} и зная вероятности р(mi) для каждого сообщения, информативность этих сообщений можно вычислить следующим образом:

Количество информации в сообщении измеряется в битах. Например, информативность в сообщения в результате подбрасывания обычной монеты составляет



Если же монета такова, что вероятность выпадения решки составляет 75%, то информативность сообщения равна

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

Дерево решений можно рассматривать с точки зрения информации о примерах. Информативность дерева вычисляется на основе вероятностей различных типов классификации. Например, если предположить, что все примеры в таблице 1 появляются с одинаковой вероятностью, то

Следовательно, информативность распределения D1 описанного в таблице 1, а значит и любого дерева, покрывающего эти примеры, составляет

Количество информации, обеспечиваемое при выборе данного свойства в корне текущего дерева, равно разности общего количества информации в дереве и количества информации необходимого для завершения классификации. Количество информации необходимое для завершения дерева, определяется как взвешенное среднее ин­формации во всех его поддеревьях. Взвешенное среднее вычисляется как сумма произ­ведений информативности каждого поддерева и процентного соотношения примеров в этом поддереве.

Предположим, что существует набор обучающих примеров С. Если корнем текущего дерева является свойство Р, которое может принимать n значений, то множество С будет разделено на подмножества 1 С2,.. , Сn}. Информация, необходимая для завершения построения дерева при выборе свойства Р, составляет

Выигрыш от использования свойства Р вычисляется как разность общей информатив­ности дерева и объема информации, необходимого для завершения построения дерева.

Возвращаясь к примеру из таблице 1, при выборе в качестве корня дерева свойства "доход" примеры будут разделены на три группы: С,={1,4,7, 11},С2={2, 3, 12, 14} и С3={5, 6, 8, 9, 10, 13}. Информация, необходимая для завершения построения де­рева, составляет

Информационный выигрыш от такого разбиения данных таблице1, составляет

Аналогично можно показать, что

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

<== предыдущая лекция | следующая лекция ==>
Построение дерева решений сверху вниз | Языки программирования для ЭС и языки представления знаний

Дата добавления: 2014-01-03; Просмотров: 301; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.004 сек.