Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE \* MERGEFORMAT 37
|
[1] Лекция 10. Способы представления исходной информации в интеллектуальных системах [1.1] 10. 1 Обучение на основе примеров [1.2] 10.2 Типы значений признаков: [1.3] 10.3 Ранговая или порядковая шкала значений признаков [1.4] 10. 4 Выборка К+ [1.5] 10.5 Выборка К- [1.6] 10.6 Кластерный анализ [1.6.1] 10.6.1 Пример процедуры кластерного анализа: . [1.6.2] 10.6.2 Диаграмма рассеивания [1.6.3] 10.6.3 Способы определения меры расстояния между кластерами [1.6.4] 10.6.4 Работа кластерного анализа опирается на два предположения. [1.6.5] 10.6.5 Рассмотрим пример. [1.6.6] 10.6.6 Способы нормирования исходных данных: . [1.6.7] 10.6.7 Методы кластерного анализа можно разделить на две группы: [1.6.8] 10.6.7.1 Иерархические агломеративные методы (Agglomerative Nesting, AGNES) [1.6.9] 10.6.7.2 Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA) [1.6.10] 10.6.8 Программная реализация алгоритмов кластерного анализа [1.7] 10.6.9 Пример вертикальной дендрограммы [1.8] 10.6.10 Методы объединения или связи [1.8.1] Метод ближнего соседа или одиночная связь. [1.8.2] Метод Варда (Ward's method). [1.8.3] Метод наиболее удаленных соседей или полная связь. [1.8.4] Метод невзвешенного попарного среднего [1.8.5] Метод взвешенного попарного среднего [1.8.6] Невзвешенный центроидный метод [1.9] 10.7 Задача обучения «без учителя» [1.10] 10.8 Алгоритм, основанный на понятии порогового расстояния [1.10.1] 10.8.1 Пример работы алгоритма, основанного на вычислении порогового расстояния. [2] Лекция 11. Алгоритмы обучения без учителя [2.1] 11.1 Алгоритм MAXMIN [2.2] 11.2 Алгоритм «К средних» [2.2.1] 11.2.1 Пример работы алгоритма «К средних» [2.2.2] 11.2.2 Проблемы алгоритма K-средних: [2.3] 11.3 Алгоритмы расстановки центров кластеров [2.4] 11.4 Алгоритм, основанный на методе просеивания [2.5] 11.5 Нечеткий алгоритм кластеризации с-means [2.5.1] 11.5.1 Классический пример с-means — т.н. «бабочка» (butterfly): [2.5.2] 11.5.2 Алгоритм ISODATA [2.6] 11.6 Распознавание с использованием решающих функций [2.7] 11.7 Построение решающих функций по критерию минимального расстояния [2.8] 11.8 Разделяющие решающие функции [2.9] 11.9 Распознавание образов [2.9.1] 11.9. 1 Метод эталонных образов [2.9.2] 11.9.2 Метод эталонных образов [2.10] 11.10 Линейные решающий функции [2.10.1] 11.10.1 Алгоритм построения линейной разделяющей функции [2.10.2] 11.10.2 Пример работы алгоритма построения линейной разделяющей функции [2.11] 11.11 Построение решающих функций методом потенциалов [2.12] 13 лекция. Компьютерные технологии в образовании [2.13] 13.1 Применение компьютеров в образовании [2.14] 13.2 Программированное обучение. Автор Б.Ф. Скиннер [2.15] 13.3 Основные формы программирования [2.15.1] 13.3.1 Линейная программа [2.15.2] 13.3.2 Разветвленная форма. Норман А. Кроудер [2.16] 13.4 Автоматизация программированного обучения [2.17] 13.5 Искусственный интеллект [2.18] 13.6 Задача-максимум создания Искусственного Интеллекта [2.19] 13.7 Автоматизированная обучающая система «Контакт» [2.20] 13.8 АОС ЭВОС и АТОС [2.21] 13.9 АОС САДКО [2.22] 13.10 PLATO [2.23] 13.11 В общем об обучающих системах [2.24] 13.12 Интеллектуальные обучающие системы (ИОС) [2.24.1] 13.12.1 Четыре этапа развития ИОС [2.24.2] 13.12.2 Принципы организации и реализации интеллектуальных систем электронного обучения [2.25] 13.13 Web 2.0 [2.25.1] 13.13. 1 Особенности Образования Web 2.0 или Образования 2.0 [2.26] 13.14 Семантический Web (Web 3.0) [2.26.1] 13.14. 1 Основыне принципы Образования 3.0 [2.27] 13.15 ИОС на осве СУБЗ [2.28] 13.16 Алгоритм муравья [2.28.1] 13.17 Модель обучения в общем виде [2.29] 13.18 Этапы создания ИОС от специалистов [2.30] 13.19 Состав группы для разработки ИОС |
Человек, решающий задачу выбора целесообразного поведения в той или иной ситуации, прежде всего, анализирует существенные и несущественные обстоятельства, влияющие на принимаемое решение. Процесс выделения существенных для данной задачи обстоятельств можно представить как разбиение входных ситуаций на классы, обладающие тем свойством, что все ситуации из одного класса требуют одних и тех же действий.
Оценка входной ситуации человеком происходит на основе совокупности сигналов, поступающих от его органов чувств. На основании этих сигналов мозг вырабатывает команды, которые обеспечивают реакцию человека на ситуацию. Сигналы поступают от рецепторов (зрительных, тактильных и др.). Совокупность таких сигналов формирует представление человека о ситуации.
Вычислительная машина, на которой моделируется аналогичный процесс, должна обладать возможностью получать описание входной ситуации от внешних «рецепторов» в виде различных наборов данных. Очевидно, объем информации, который получает компьютер, несоизмеримо меньше объемов информации, с которыми имеет дело человек; кроме того, такая информация будет представлена исключительно в численной форме.
Для того, чтобы эффективно оценить, относятся ли различные ситуации к одному классу, интеллектуальная система должна иметь возможность рассмотреть и оценить ряд конкретных примеров таких ситуаций, включенных в обучающее множество.
Обучение на основе примеров является типичным случаем индуктивного обучения и широко используется в интеллектуальных системах. На основе предъявленных примеров (и, возможно, контрпримеров) интеллектуальная система должна сформировать общее понятие, охватывающее примеры и исключающее контрпримеры.
Источником примеров, на которых осуществляется обучение, может быть учитель то есть лицо, которое заранее знает концепцию формируемого понятия и подбирает наиболее удачные обучающие выборки.
Источником примеров для обучения может быть внешняя среда, с которой взаимодействует интеллектуальная система. В этом случае обучающие выборки формируются случайным образом в зависимости от внешних факторов. Обучение на таких выборках существенно сложнее.
Наконец, источником примеров для обучения может стать сама интеллектуальная система. Например, в случае взаимодействия интеллектуального робота с внешней средой действия самого робота могут привести к созданию обучающей выборки, то есть образуется множество сходных ситуаций с известными результатами, которые можно затем обобщить.
Для системы машинного обучения принципиально важным является вопрос, что поступает на вход системы, в каком виде предъявляются примеры понятия, включенные в состав обучающего множества.
Все основные методы решения задач индуктивного построения понятий базируются на концепции признакового описания примера понятия, а именно: любой элемент обучающей выборки, который может быть представлен в системе, полностью определяется набором свойств, или признаков. Такое задание объекта исследования называется признаковым описанием объекта.
Значения, которые могут принимать признаки объекта, относятся к трем основным типам:
количественные или числовые,
качественные
шкалированные.
В случае числовых признаков на множестве значений признаков может быть введена метрика, позволяющая дать количественную оценку значения признака. Часто такие значения являются результатом измерений физических величин, таких, как длина, вес, температура и др.
В случае, если признаки могут иметь качественный характер, но при этом их значения можно упорядочить друг относительно друга, говорят, что такие значения образуют ранговую или порядковую шкалу.
Примерами таких шкал порядка могут быть ряды типа {большой, средний, маленький} или {горячий, теплый, холодный}. С помощью таких шкал порядка можно судить, какой из двух объектов является наилучшим, но нельзя оценить, сколь близки или далеки эти объекты по некоторому критерию.
Третий случай заключается в том, что значения признаков имеют чисто качественный характер, связать эти значения между собой не удается. Примерами таких значений могут быть цвет = {красный, желтый, зеленый} или материал = {стекло, дерево, пластмасса, железо}.
Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов.
В отличие от задач классификации, кластерный анализ не требует априорных предположений о наборе данных, не накладывает ограничения на представление исследуемых объектов, позволяет анализировать показатели различных типов данных (интервальным данным, частотам, бинарным данным). При этом необходимо помнить, что переменные должны измеряться в сравнимых шкалах.
Допустим, мы имеем набор данных А, состоящий из 14-ти примеров, у которых имеется по два признака X и Y. Данные по ним приведены в таблице.
Данные в табличной форме не носят информативный характер. Представим переменные X и Y в виде диаграммы рассеивания
На рисунке мы видим несколько групп "похожих" примеров. Примеры (объекты), которые по значениям X и Y "похожи" друг на друга, принадлежат к одной группе (кластеру); объекты из разных кластеров не похожи друг на друга.
Критерием для определения схожести и различия кластеров является расстояние между точками на диаграмме рассеивания. Это сходство можно "измерить", оно равно расстоянию между точками на графике. Способов определения меры расстояния между кластерами, называемой еще мерой близости, существует несколько.
Наиболее распространенный способ - вычисление евклидова расстояния между двумя точками i и j на плоскости, когда известны их координаты X и Y:
Кластер имеет следующие математические характеристики:
- центр,
- радиус,
- среднеквадратическое отклонение,
- размер кластера.
Центр кластера - это среднее геометрическое место точек в пространстве переменных.
Радиус кластера - максимальное расстояние точек от центра кластера.
Кластеры могут быть перекрывающимися. Такая ситуация возникает, когда обнаруживается перекрытие кластеров. В этом случае невозможно при помощи математических процедур однозначно отнести объект к одному из двух кластеров. Такие объекты называют спорными.
Спорный объект - это объект, который по мере сходства может быть отнесен к нескольким кластерам.
Размер кластера может быть определен либо по радиусу кластера, либо по среднеквадратичному отклонению объектов для этого кластера. Объект относится к кластеру, если расстояние от объекта до центра кластера меньше радиуса кластера. Если это условие выполняется для двух и более кластеров, объект является спорным.
Неоднозначность данной задачи может быть устранена экспертом или аналитиком.
Первое предположение - рассматриваемые признаки объекта в принципе допускают желательное разбиение пула (совокупности) объектов на кластеры
В начале лекции мы уже упоминали о сравнимости шкал, это и есть Второе предположение - правильность выбора масштаба или единиц измерения признаков. Выбор масштаба в кластерном анализе имеет большое значение.
Представим себе, что данные признака х в наборе данных А на два порядка больше данных признака у: значения переменной х находятся в диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1.
Тогда, при расчете величины расстояния между точками, отражающими положение объектов в пространстве их свойств, переменная, имеющая большие значения, т.е. переменная х, будет практически полностью доминировать над переменной с малыми значениями, т.е. переменной у. Таким образом из-за неоднородности единиц измерения признаков становится невозможно корректно рассчитать расстояния между точками.
Эта проблема решается при помощи предварительной стандартизации переменных. Стандартизация (standardization) или нормирование (normalization) приводит значения всех преобразованных переменных к единому диапазону значений путем выражения через отношение этих значений к некой величине, отражающей определенные свойства конкретного признака. Существуют различные способы нормирования исходных данных.
Наиболее распространенный: деление исходных данных на среднеквадратичное отклонение соответствующих переменных
Наряду со стандартизацией переменных, существует вариант придания каждой из них определенного коэффициента важности, или веса, который бы отражал значимость соответствующей переменной. В качестве весов могут выступать экспертные оценки, полученные в ходе опроса экспертов - специалистов предметной области. Полученные произведения нормированных переменных на соответствующие веса позволяют получать расстояния между точками в многомерном пространстве с учетом неодинакового веса переменных
- иерархические;
- неиерархические.
Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие
Эта группа методов характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров.
В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.
Эти методы являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.
Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломеративные методы реализованы в пакете SPSS, дивизимные методы - в пакете Statgraf.
Иерархические методы кластеризации различаются правилами построения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о "схожести" объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).
Иерархические методы кластерного анализа используются при небольших объемах наборов данных.
Преимуществом иерархических методов кластеризации является их наглядность.
Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа.
Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.
Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально.
Числа 11, 10, 3 и т.д. соответствуют номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.
Когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Возникает следующий вопрос - как определить расстояния между кластерами? Существуют различные правила, называемые методами объединения или связи для двух кластеров.
Здесь расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов.
В результате работы этого метода кластеры представляются длинными "цепочками" или "волокнистыми" кластерами, "сцепленными вместе" только отдельными элементами, которые случайно оказались ближе остальных друг к другу.
В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения (Ward, 1963). В отличие от других методов кластерного анализа для оценки расстояний между кластерами, здесь используются методы дисперсионного анализа. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров и "стремится" создавать кластеры малого размера.
Здесь расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями"). Метод хорошо использовать, когда объекты действительно происходят из различных "рощ". Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является "цепочечным", то этот метод не следует использовать.
(метод невзвешенного попарного арифметического среднего - unweighted pair-group method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)).
В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Этот метод следует использовать, если объекты действительно происходят из различных "рощ", в случаях присутствия кластеров "цепочного" типа, при предположении неравных размеров кластеров.
(метод взвешенного попарного арифметического среднего - weighted pair-group method using arithmetic averages, WPGM A (Sneath, Sokal, 1973)). Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере).
Этот метод рекомендуется использовать именно при наличии предположения о кластерах разных размеров.
(метод невзвешенного попарного центроидного усреднения - unweighted pair-group method using the centroid average (Sneath and Sokal, 1973)).
В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.
Важность алгоритмов “обучения без учителя” в том, что реальные признаки, описывающие объекты распознавания, очень часто бывают именно количественными, или числовыми. Известно, что человек плохо воспринимает информацию, представленную в виде больших наборов чисел. Первым и крайне важным этапом решения задачи обобщения в таком случае будет переход от количественных признаков к признакам качественным или хотя бы к шкалируемым. Здесь большую помощь могут оказать алгоритмы рассматриваемого типа.
Дадим более строгую формулировку задачи обучения «без учителя».
Пусть обучающая выборка содержит М объектов: X = {X1,X2,…,Хn}- Каждый из этих объектов представляет собой n-мерный вектор Xi значений признаков:
где xij — значение j-ro признака для i-го объекта, п — количество признаков, характеризующих объект.
Признаки, используемые для описания объекта, чисто количественные, к ним применимы введенные в предыдущей главе меры близости.
Требуется в соответствии с заданным критерием разделить набор X на классы, количество которых заранее неизвестно. Под критерием подразумевается мера близости всех объектов одного класса между собой. Будем считать, что работа алгоритма завершена успешно, если классы, сформированные в результате работы алгоритма, достаточно компактны и, возможно, выполнены некоторые дополнительные критерии.
При решении задачи обучения «без учителя» самыми несложными являются алгоритмы, основанные на мерах близости. Для достижения цели - компактного формирования классов — введем понятие точки-прототипа, или точки в n-мерном пространстве признаков, являющейся наиболее «типичной» представительницей построенного класса. В дальнейшем расстояние от объекта до класса будет заменяться расстоянием от объекта до точки-прототипа. Точка-прототип может быть сопоставлена каждому сформированному классу, и при этом вовсе не обязательно существование реального объекта, соответствующего точке-прототипу.
Пороговый алгоритм — один из самых несложных алгоритмов, базирующихся на понятии меры близости. Критерием отнесения объекта к классу здесь является пороговое расстояние Т. Если объект находится в пределах порогового расстояния от точки-прототипа некоторого класса, то такой объект будет отнесен к данному классу. Если исследуемый объект находится на расстоянии, превышающем Т, он становится прототипом нового класса.
Самая первая точка-прототип может выбираться произвольно. Результатом работы такого алгоритма будет разбиение объектов выборки X на классы, где в каждом классе расстояние между точкой-прототипом и любым другим элементом класса не превышает Т. Пороговое расстояние Т определим как половину расстояния между двумя наиболее удаленными друг от друга точками обучающей выборки.
Алгоритм
Выбрать точку-прототип первого класса (например, объект Х1 из обучающей выборки). Количество классов К положить равным 1. Обозначить точку-прототип Z1.
Определить наиболее удаленный от Z1 объект Xf по условию
D(Z1,Xf) = max D(Z1, Xi),
где D(Z1,Xf) - расстояние между Z1 и Xf, вычисленное одним из возможных способов. Объявить Xf прототипом второго класса. Обозначить Xf как Z2. Число классов К = К + 1.
Определить пороговое расстояние Т = D(Z1,Z2)/2.
Построить
Пусть каждый объект из множества объектов, представленных в таблице, задан двумя признаками (модель - точка на плоскости)
Выберем в качестве точки-прототипа первого класса точку Х1 из обучающей выборки (обозначается далее Z1). В таблице представлены расстояния от этой точки до объектов Х2 — Х8.
Наиболее удаленным объектом для Z1 будет Х8.
Пороговое расстояние
Точка Х8 становится точкой-прототипом второго класса и обозначается далее Z2.
Рассматриваем точки множества
Достоинства рассмотренного алгоритма:
простота реализации и небольшой объем вычислений.
Недостатки:
- не предусмотрено уточнение разбиения. В результате расстояние от объекта до точки-прототипа класса может оказаться больше, чем расстояние от этого объекта до точки-прототипа другого класса.
- Результат, кроме того, сильно зависит от порядка рассмотрения объектов X, а также от способа вычисления порогового расстояния (можно использовать и другие формулы для подсчета Т).
Из этого следует, что полезно было бы использовать алгоритмы, допускающие многократную коррекцию формируемых классов, например, можно было бы менять пороговое расстояние Т и проводить многократное уточнение разбиения.
Рассмотрим алгоритм, более эффективный по сравнению с предыдущим и являющийся улучшением порогового алгоритма. Исходными даннымы для работы алгоритма будет, как и раньше, выборка X. Объекты этой выборки следует разделить на классы, число и характеристики которых заранее неизвестны.
На первом этапе алгоритма все объекты разделяются по классам на основе критерия минимального расстояния от точек-прототипов этих классов (первая точка-прототип может выбираться произвольо). Затем в каждом классе выбирается объект, наиболее удаленный от своего прототипа. Если он удален от своего прототипа на расстояние, превышающее пороговое, такой объект становится прототипом нового класса.
В этом алгоритме пороговое расстояние не является фиксированным, а определяется на основе среднего расстояния между всеми точками-прототипами, то есть корректируется в процессе работы алгоритма. Если в ходе распределения объектов выборки X по классам были созданы новые прототипы, процесс распределения повторяется. Таким образом, в алгоритме MAXMIN окончательным считается разбиение, для которого в каждом классе расстояние от точки-прототипа до всех объектов этого класса не превышает финального значения порога Т.
Алгоритм
Выбрать точку-прототип первого класса (например, объект Х1 из обучающей выборки). Количество классов К положить равным 1. Обозначить точку-прототип Z1.
Определить наиболее удаленный от Z1 объект Xf по условию
D(Z1,Xf) = max D(Z1, Xi),
где D(Z1,Xf) - расстояние между Z1 и Xf, вычисленное одним из возможных способов. Объявить Xf прототипом второго класса. Обозначить Xf как Z2. Число классов К = К + 1.
Рассмотрим работу алгоритма MAXMIN на примере. Как и в предыдущем случае выберем объекты, которые заданы двумя признаками. Обучающая выборка представлена на рис.
- необходимо заранее знать количество кластеров.
- алгоритм очень чувствителен к выбору начальных центров кластеров. Классический вариант подразумевает случайный выбор кластеров, что очень часто являлось источником погрешности. Как вариант решения, необходимо проводить исследования объекта для более точного определения центров начальных кластеров.
- не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному.
С последней проблемой k-means успешно справляется алгоритм с-means. Вместо однозначного ответа на вопрос, к какому кластеру относится объект, он определяет вероятность того, что объект принадлежит к тому или иному кластеру. Таким образом, утверждение «объект А принадлежит к кластеру 1 с вероятностью 90%, к кластеру 2 — 10% » верно и более удобно.
(Iterative Self-Organizing Data Analysis Techniques) основывается на алгоритме k средних, но включает набор оказавшихся полезными на практике эвристик и параметры по их настройке. Одним из задаваемых априори параметров является желаемое число кластеров K.
Это число выступает в качестве рекомендации: в результате работы алгоритма может быть построено как меньшее, так и большее число кластеров, но оно будет не сильно отличаться от значения K. Сам алгоритм здесь детально описываться не будет (в целом, в нем используются те же шаги, что и в алгоритме k средних); приведем лишь основные эвристики.
- Ликвидируются кластеры, в состав которых входит менее чем заданное число элементов.
- Для каждого текущего кластера определяется направление максимальной вытянутости. Наиболее вытянутый кластер может быть расщеплен на два.
- Решение о расщеплении принимается с учетом размера кластера в направлении вытянутости (этот размер может сравниваться с фиксированным порогом и отклонением от среднего размера всех кластеров, а также общего числа кластеров, которое должно быть мало (с учетом параметра K).
- Попарно сливаются кластеры, расстояние между центрами которых меньше заданного порога, если число кластеров велико (с учетом параметра K).
Использующиеся в алгоритме ISODATA эвристики помогают не только подбирать более подходящее число классов, но и находить более приемлемое решение, несколько ослабляя (но не убирая полностью) зависимость от начальной гипотезы.
Алгоритмы, рассмотренные в этой главе, обладают одним общим свойством: в их помощью для обучающей выборки Х решается задача классификации, то есть строится разбиение примеров обучающей выборки на классы. Вспомним, что алгоритмы обобщения должны успешно решать задачу распознавания, то есть задачу распределения вновь предъявляемых примеров по классам. Последнее требует наличия четко сформулированного решающего правила, или алгоритма, позволяющего отвести новый Х к одному из классов.
Задача минимизации количества решающих функций, достаточных для классификации образов, может быть очень важна, особенно если количество классов d велико. Если представить себе, с каким количеством классов объектов (или понятий) имеет дело человек, становится ясно, что решение этой проблемы в том или ином виде потребуется при разработке универсальной системы машинного обучения. Мы, однако, этот вопрос здесь рассматривать не будем, а перейдем к проблеме распознавания образов.
Прямого ответа на этот вопрос можно избежать, если конструировать методы распознавания на основе неких эвристических соображений. Два наиболее широко распространенных эвристических метода – это метод эталонных образов и метод ближайшего соседа.
Метод эталонных образов – это один из эвристических методов построения решающих правил. В основу этого метода положена идея, которая заключается в том, что некоторая совокупность объектов, объединенных в отдельный класс, может быть представлена одним или несколькими эталонными объектами.
Эти эталонные объекты являются наиболее типичными представителями класса. Типичность эталонного объекта означает, что он в среднем максимально похож на все объекты класса.
Поскольку сходство двух объектов может трактоваться как величина, противоположная расстоянию между ними в пространстве описаний (образов), то эталон – это объект, для которого минимально среднее расстояние до других объектов.
Классы, однако, могут обладать разными свойствами. Простейшим свойством является характерный размер класса, который может быть оценен как
В соответствии с данным решающим правилом просматривается вся обучающая выборка, в ней находится образ, расположенный наиболее близко к данному и устанавливается, к какому классу он принадлежит (это известно, поскольку он находится в обучающей выборке). Этот класс и приписывается новому образу.
Метод ближайшего соседа весьма чувствителен к выбросам, то есть тем образам обучающей выборки, для которых указаны ошибочные классы. В методе k-ближайших соседей выбирается k образов обучающей выборки, наиболее близко расположенных к классифицируемому образу, и определяется, к какому классу относится больше всего из них. Поскольку выбросов, как правило, значительно меньше, чем правильных примеров, можно надеяться, что среди k ближайших соседей выбросов будет мало, и они не окажут влияния на результат классификации.
Возможность автоматизации любого вида деятельности появляется в том случае, когда выполняемые человеком функции могут быть в достаточной степени формализуемы и адекватно воспроизведены с помощью технических средств, при условии выполнения требований по качеству достигаемого результата. Для процесса передачи знаний эта возможность появилась вместе с появлением вычислительной техники – в середине прошлого века.
Первые эксперименты по применению компьютеров в образовании относятся к концу 50-х годов. Несмотря на то, что техническая база ЭВМ и программное обеспечение того времени явно не соответствовали успешному решению поставленной проблемы в целом, исследования в этой области начались во всех развитых странах. Выделим наиболее значимые этапы развития работ в этой области и проследим за изменением целей и задач, которые ставили перед собой исследователи и разработчики.
Первый этап исследования возможностей создания обучающих систем приходится на 50-е и 60-е годы двадцатого столетия. Профессор Б.Ф. Скиннер в 1954 году выдвинул идею, получившую название программированного обучения. Она заключалась в призыве повысить эффективность управления учебным процессом путем построения его в полном соответствии с психологическими знаниями о нем, что фактически означает внедрение кибернетики в практику обучения . Это направление начало активно развиваться в США, а потом и в других странах. И уже тогда одним из основных признаков программированного обучения считалась автоматизация процесса обучения .
В основу технологии программированного обучения Б. Ф. Скиннер положил два требования:
уйти от контроля и перейти к самоконтролю;
перевести педагогическую систему на самообучение учащихся.
Главный элемент программированного обучения — обучающая программа, представляющая собой упорядоченную последовательность задач. Для программированного обучения существенно наличие «дидактической машины» (или программированного учебника).
Различают три основные формы программирования:
1)линейное;
2)разветвленное;
3) смешанное.
Разработка линейных программ принадлежит самому Б.Ф.Скиннеру: обучаемый знакомится с каждой порцией материала в заданной последовательности:
Линейная программа в понимании Б.Ф. Скиннера характеризуется следующим:
— дидактический материал делится на незначительные дозы, называемые шагами (steps), которые учащиеся преодолевают относительно легко, шаг за шагом (step by step);
— вопросы или пробелы, содержащиеся в отдельных рамках (frame) программы, не должны быть очень трудными, чтобы учащиеся не потеряли интереса к работе;
— учащиеся сами дают ответы на вопросы и заполняют пробелы, привлекая для этого необходимую информацию;
— в ходе обучения учащихся сразу же информируют, правильны или ошибочны их ответы;
— все обучающиеся проходят по очереди все рамки программы, но каждый делает это в удобном для него темпе;
— значительное число указаний в начале программы, облегчающих получение ответа, постепенно ограничивается;
— во избежание механического запоминания информации одна и та же мысль повторяется в различных вариантах в нескольких рамках программы.
Линейная программа как бы предполагает, что учащийся не сделает ошибки в ответе. В 1954 г. Б.Ф.Скиннер проверил свою программу на студентах университета и получил отрицательный результат. Линейная программа успеха не принесла.
Разработку разветвленной формы осуществлял другой представитель американской технологии программированного обучения — Норман А. Кроудер. В его схеме S — R — Р связи между стимулом, реакцией и продуктом осуществляются мыслительными операциями. Кроме того, он предполагал дифференцированный подход к обучаемым. Разветвленная программа может быть представлена следующим образом (см. схему).
В разветвленной программе операционные кадры построены по избирательному принципу, т.е. учащийся должен выбрать один из предложенных ему ответов. В зависимости от выбранного ответа программа разветвляется .
Особенностями разветвленной обучающей программы являются:
- сравнительно крупное дробление учебного материала;
- необязательное выполнение всех кадров (индивидуализация обучения);
- наличие возврата в программу;
- дифференциация продвижения учащегося по программе в зависимости от степени выполнения программы.
Автоматизация программированного обучения началась с использования обучающих и контролирующих устройств различного типа.
Они достаточно широко применялись в 60–70-е годы, хотя из-за ограниченных возможностей не обеспечивали достаточной эффективности и адекватности результатов контроля реальному уровню знаний обучаемого.
Фактически применение таких устройств как в нашей стране, так и за рубежом не вышло за рамки обучения разным навыкам, а также простейших методов контроля, в основном выборочного типа.
В это же время (60–70-е годы) начали развиваться идеи искусственного интеллекта.
Были разработаны основные модели представления знаний, появились первые системы, использующие методы искусственного интеллекта. Это было время эйфории. Казалось, еще немного, каких-то 10-20 лет, и будет создан искусственный разум, которому можно будет перепоручить многие обязанности человека, по крайней мере, те из них, которые не требуют творческого подхода.
Благодаря этой атмосфере всеобщей воодушевленности стоящие перед разработчиками обучающих систем цели были сформулированы следующим образом. Разработать такую обучающую систему, которая могла бы полностью имитировать преподавателя, т.е. обладала бы достаточным набором знаний не только в предметной области, но и в педагогике, и могла бы в рамках предметной области общаться с обучаемым на естественном языке.
Это была задача-максимум, но она определила цель, к которой следовало стремиться. В результате проводимых исследований была разработана структура обучающих систем и предложены некоторые методы решения этой проблемы. Но, как и в области исследований по искусственному интеллекту, реализация общих идей столкнулась с огромными практическими трудностями. В процессе создания первых прототипов АОС стало ясно, насколько сложными являются задачи представления предметных знаний, организации обратной связи с обучаемым (в том числе, полноценного диалога, для которого явно не хватало лингвистических знаний). Поэтому созданные в то время системы очень сильно отличались от идеала.
Тем не менее, в 60-е годы было разработано большое количество специализированных пакетов программ, ориентированных на создание и сопровождение прикладных обучающих программ – автоматизированных учебных курсов (АУК) на базе ЭВМ третьего поколения.
Одними из самых известных в нашей стране проектов использования вычислительной техники и средств коммуникации в обучении является проект PLATO в наиболее развитой версии – PLATO-IV, а также отечественные автоматизированные обучающие системы АОС-ВУЗ, АОС-СПОК, АСТРА, САДКО и другие.
Автоматизированная обучающая система «Контакт» была создана сотрудниками Рижского политехнического института в конце 1960-х годов на базе компьютеров «Минск-32»; в качестве периферийных устройств использовались электрические пишущие машинки, телетайпы и дисплеи. С помощью разработанной системы осуществлялся контроль знаний по комплексу вопросов предварительно занесённых в её базу данных; система поддерживала разветвлённую логику выдачи обучающемуся вопросов.
Так на основании правильности ответов на первые вопросы программа формировала представление о подготовленности учащегося и выдавала те или иные вопросы исходя из уровня его знаний. Доработанная в 1982 году АОС «Контакт/ОС» включала 40 обучающе-контролирующих и 29 контролирующих комплексов вопросов по языкам программирования, операционным системам, философии, инженерной графике и другим дисциплинам.
В Белорусском Государственном Университете были созданы АОС ЭВОС (Экспериментальная Вычислительная Обучающая Система) и АТОС (Автоматизированная Телевизионная Обучающая Система). ЭВОС использовала специальные пульты преподавателя и учащихся, соединённые с единым устройством управления, в роли которого выступал компьютер. По такому же принципу был построена АТОС, использовавшая в качестве терминала телевизор «Юность» и специально разработанную клавиатуру.
Для АОС САДКО (Система Автоматизированного Диалога и Коллективного Обучения), которая была разработана в ВЦ Минвуза РСФСР, использовался другой подход, суть которого заключалась в совместном использовании компьютера и учебного пособия на бумажном носителе. Обучаемый изучал определённый учебный материал по пособию, выполнял задание в рабочей тетради.
По завершению отработки учебного материала происходил ввод ответа с помощью специального пульта в АОС в виде формул, чисел, букв или текста. Ответ проверялся АОС и, в зависимости от его верности, выдавала информацию о решении, а также о номере страницы пособия, на которую учащийся должен был перейти для продолжения обучения. Данная программа ориентировалась на самостоятельное индивидуальное обучение без ограничения времени на выполнение заданий.
Успехи советской космической программы не только подтолкнули к созданию Internet, но и встряхнули всю систему высшей школы США. Ее реформирование привело к созданию автоматизированной системы обучения PLATO (Programmed Logic for Automated Teaching Operations) в университете штата Иллинойс. Этот проект, финансировавшийся долгое время из фондов Пентагона и просуществовавший до 1990 года оказался убыточным. Однако некоторые его находки (например, онлайновые форумы и доски для обмена сообщениями) стали классикой современных ИТ. Самым же значительным наследием PLATO оказалось изобретение программного обеспечения для групповой работы (groupware).
Реализацией проекта системы PLATO занималась Control Data Corporation (CDC) — она производила компьютеры, на которой работала эта система. Президент корпорации Уильям Норрис (англ.) планировал совершить прорыв в компьютерном мире. Последняя работающая система была отключена в 2006 году (всего через месяц после смерти Норриса), но за это время благодаря PLATO были введены такие базовые понятия как форум, онлайн-тестирование, электронная почта, чат, мгновенное сообщение, удалённый рабочий стол, многопользовательская игра. Именно для компьютеров PLATO в 1973 году была создана первая игра c трёхмерной графикой Spasim a также впервые адаптированы такие известные игры, как Маджонг и Солитер.
По сути дела эти и многие другие обучающие системы были системами селективного (выбирающего) типа. В таких системах определение методики обучения в целом и содержание обучающих воздействий в частности оставлялось педагогу, а их реализация и оценка результатов производилась средствами АОС. Связующим звеном между системой и педагогом была специальная форма представления информации – обучающий курс, – в который человеком "закладывались" все обучающие воздействия и условия смены их последовательности по линейной или ветвящейся программе.
Кроме систем селективного типа были созданы продуцирующие обучающие системы, в которых диалог с обучаемым не программируется, а формируется по нескольким алгоритмам в соответствии с набором операций и фактов, заложенных в систему. Подобные обучающие системы предназначались для некоторых специфических предметных областей, которые по тем или иным причинам оказались исключительно подходящими для такого типа программирования.
В качестве примеров можно привести систему Ликлайдера для обучения аналитической геометрии и систему Битена и Лэйна, обучающую произношению слов иностранного языка .
В 1970 году Дж. Карбонеллом было сформулировано общее представление об интеллектуальных обучающих системах (ИОС). Он представил свою систему SCHOLAR, на примере которой была продемонстрирована эффективность использования методов искусственного интеллекта (ИИ) в такой области как обучение. Если началом исследований в области ИИ принято считать 1955 год, когда Ньюэлл и Саймон приступили к исследованиям «сложных процессов обработки информации» в Технологическом институте Карнеги, то 1970-й можно считается годом рождения нового научного направления, появившегося на стыке программированного обучения и ИИ.
В первых ИОС, обучающие воздействия предлагаются не педагогом, а выбираются или генерируются обучающей системой в зависимости от целей обучения и с учетом знаний учащегося. Для этого в обучающей системе представлены знания о том, чему учить, как учить и знания о самом учащемся, а также имеются некоторые умения, позволяющие вести диалог с учащимся. Такие системы позволяют адаптивно выдавать учебные воздействия, сопровождать решение задач, производить глубокую диагностику знаний обучаемого, которая подразумевает реализацию еще целого ряда «интеллектуальных» возможностей.
Следующий, второй этап в развитии систем обучения включал период с начала 1970-х до середины 1980-х. В эти годы в истории искусственного интеллекта наступили трудные времена, соответственно и идея создания интеллектуальных обучающих систем фактически потерпела временное фиаско, что нашло свое отражение в деградации понятия автоматизированного обучения. Автоматизированными обучающими системами начали называть любые программы, предназначенные для информационной или функциональной поддержки процесса обучения: тесты, электронные учебники, лабораторные практикумы и т.п.
Третий этап – имеет начало во второй половине 1980-х и завершение в 1990-е годы. Данному периоду характерны две основные тенденции:
- широкое распространение персональных компьютеров (ПК) и развитие вычислительных сетей ориентирует обучающие системы на работу в сети с использованием общепринятых стандартов представления и передачи данных;
- возросшие аппаратные возможности привели к тому, что одним из основных направлений развития обучающих систем стало применение в них новых компьютерных технологий (в первую очередь, гипертекста, мультимедиа, технологий искусственного интеллекта).
Современный, четвертый этап, берет начало в 1990-х годах. Содержание этого этапа тесно связано с развитием вычислительных сетей и, в частности, сети Internet, что позволило обучающим системам подняться на новый уровень. По сравнению с локальными обучающими системами, в распределенных происходит качественное изменение функциональных возможностей, благодаря объединению сетевых ресурсов для решения возникающих перед обучающей системой задач. Широкое внедрение средств телекоммуникаций позволило значительно расширить круг пользователей системы.
Выделяется несколько основных парадигм организации и реализации интеллектуальных систем электронного обучения:
Основанная на концепции специализированных экспертных систем.
Основанная на гипертексте и гипермедиа (Web-ориентированная).
Интегрированная на использовании экспертных систем и гипертекста/гипермедиа.
Использующая модели обучаемого.
На основе интеграции экспертных систем с системами обучения.
Использующая интеллектуальных агентов.
Используются следующие основные компоненты: предметная область проектирования, обучаемый проектировщик, сценарий процесса обучения.
Возможности Интернета, как показало время, практически безграничны и позволяют перейти к использованию принципиально новых технологий обучения, коренным образом видоизменяя его парадигму. Новые подходы, основанные на информационных технологиях, особенно ускорились с появлением широкополосного Интернета и технологий Web2.0, которые в корне видоизменили многие принципы, положенные в основу классического образования.
С приходом Web 2.0 (2005-2006 гг.) почти у каждого пользователя Сети появилась возможность создавать свой контент, неограниченному количеству пользователей иметь доступ к контенту и совместной с ним работы, создавать гибридный контент, сочетающий различные форматы передачи данных – текстовый формат с графическим, цветовым, визуальным или же звуковым. Web 2.0 создал такие возможности для коммуникации и работы в Интернете, которые затем привели к формированию на его основе образовательного подхода, получившего аналогичное название Образование Web 2.0 или просто Образование 2.0. (термин был придуман канадским педагогом Стефеном Доунсом) .
- быстрого создания пользовательского контента;
- редактирования;
- совместной работы над любым текстом или проектом;
- общения;
- хранения больших объемов информации непосредственно в Сети; а не на электронных носителях;
- легкости в работе с контентом;
- распространения дружественных пользователям интерфейсов;
- усиления аудиовизуального формата передачи данных;
- обнародования любой информации в сети.
Эти возможности и некоторые другие намного увеличиваются, и традиционная приватная информация или информация для избранных становится публичной и доступной всем желающим.
В сети уже наблюдаются разговоры о том, что эпоха Web 2.0 заканчива-ется – наступает пора Web 3.0. И если концепция Web 2.0 была построена на социализации, то Web 3.0 или семантический Web , подразумевает всеобщую персонализацию сети. Новые интернет-сервисы агрегируют данные о каждом пользователе и автоматически подстраиваются к его предпочтениям: например, по запросу пользователя о покупке автомобиля поисковая система должна выдать ответ в виде адреса ближайшего автосалона. Web 3.0 – это технологии, которые позволяют идентифицировать пользователя не как абстрактного посетителя, а как личность и таким образом выдать ему более точную информацию. Чем больше информации пользователь сообщит о себе, тем более точное решение получит от интернет-сервисов, причем данные собираются «… не за счет «набивания» контента пользователем, а в силу того, что система отслеживает выбор и действия пользователей» . Следовательно, Web 3.0 является совершенно другой концептуальной моделью функционирования сети Интернет.
- принцип торента – равный обмен информацией.
- принцип социальной сети – организация широкой сети контактов по функциональному признаку (хобби, решение задачи).
- принцип Твиттера – короткая, емкая информация с возможностью рас-крыть тему при необходимости.
- принцип Блога – обучение через личный опыт и практику.
- принцип Вики – возможность дополнить и откорректировать информа-цию.
- принцип Поисковика – легкий доступ к необходимой информации.
- принцип Комментов – возможность видеть оценку информации другими членами сообщества.
Интеллектуальные обучающие системы, построенные на основе СУБЗ, ориентированы на решение большого круга задач. Для их эффективного решения необходимо использовать определенные методы и операции, основными из которых являются:
- методы машинного обучения,
- прогнозирование,
- планирование,
- формирование и валидация баз знаний.
Важной особенностью систем, использующих знания, является их способность к обучению. Эти способности дают системам возможность изменяться при взаимодействии с окружающим миром, а также в процессе приобретения опыта на основе своих внутренних состояний и действий.
В задачах обучения могут использоваться многие представления знаний. При обучении классификации объектов реального мира, например, могут использоваться выражения из теории предикатов, фреймы, объекты, деревья решений и др. Планы решения могут представляться последовательностями выполняемых действий, треугольными таблицами, а эвристики – правилами вывода.
Другим примером приобретения знаний (решений новых задач), с использованием взвешенных связей, является алгоритм муравья. В основе этого алгоритма – умение муравьев находить пищу на большом расстоянии от муравейника и возвращаться обратно. Программный муравей – агент является частью большой системы (колонии муравьев) и используется для решения каких-либо проблем. Он руководствуется набором простых правил, при выборе пути в графе. Муравей поддерживает список узлов, которые он уже посетил, поэтому он должен проходить через каждый узел только один раз.
Интеллектуальные обучающие системы (ИОС) на основе баз знаний являются сложными кибернетическими системами, имеющими особенности на всех этапах их жизненного цикла. Специалистами выделяются следующие этапы создания ИОС:
- вербальное описание предметной области;
- структурирование вербального описания предметной области с целью формирования учебных объектов;
- формирование метаданных об учебных объектах;
- создание базы знаний ИОС;
- создание тестовых объектов (заданий) для выявления степени усвоения учебного объекта.
Для разработки ИОС создается группа разработчиков в состав которой обычно входят:
- эксперт – преподаватель, специалист, который хорошо знает рассматриваемую предметную область и являющийся, в настоящее время, основным носителем знаний для ИОС;
- инженер по знаниям или аналитик – является специалистом в области искусственного интеллекта, выступающий в роли промежуточного звена между экспертом и базой знаний;
- программист – выполняет настройку инструментальной среды при создании конкретной ИОС и разрабатывает недостающие программные блоки;
- пользователь – представитель специалистов (преподавателей) для которых разрабатывается система.
Вербальное описание предметной области. Важным является создание описания, удовлетворяющего требованиям полноты и точности [7,10,15]. На этом этапе определяется множество областей знаний, которые будут представлены в создаваемой системе обучения. Эти знания могут быть получены из различных источников: от экспертов (преподавателей дисциплины, специалистов-практиков); из текстовых и графических источников (литературы, технической документации, статей, схем, чертежей); электронных источников (Интернет, баз данных, оцифрованного текста, графики, видео и др.); электронных, компьютерных систем восприятия действительности.
Предметный указатель