Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Способы представления исходной информации в интеллектуальных системах
Содержание
- 1. Способы представления исходной информации в интеллектуальных системах
- 2. Человек, решающий задачу выбора целесообразного поведения в
- 3. Оценка входной ситуации человеком происходит на основе
- 4. Вычислительная машина, на которой моделируется аналогичный процесс,
- 5. Для того, чтобы эффективно оценить, относятся ли
- 6. Обучение на основе примеров является типичным случаем
- 7. Источником примеров, на которых осуществляется обучение, может
- 8. Источником примеров для обучения может быть внешняя
- 9. Наконец, источником примеров для обучения может стать
- 10. Для системы машинного обучения принципиально важным является
- 11. Значения, которые могут принимать признаки объекта, относятся
- 12. В случае, если признаки могут иметь качественный
- 13. Третий случай заключается в том, что значения
- 14. Слайд 14
- 15. Слайд 15
- 16. Термин кластерный анализ, впервые введенный Трионом (Tryon)
- 17. Рассмотрим пример процедуры кластерного анализа.Допустим, мы имеем
- 18. Слайд 18
- 19. Данные в табличной форме не носят информативный
- 20. На рисунке мы видим несколько групп "похожих"
- 21. Наиболее распространенный способ - вычисление евклидова расстояния
- 22. Наиболее распространенный способ - вычисление евклидова расстояния
- 23. Кластер имеет следующие математические характеристики: центр, радиус,
- 24. Спорный объект - это объект, который по
- 25. Слайд 25
- 26. Работа кластерного анализа опирается на два предположения.
- 27. Рассмотрим пример. Представим себе, что данные признака
- 28. Эта проблема решается при помощи предварительной стандартизации
- 29. Наряду со стандартизацией переменных, существует вариант придания
- 30. Методы кластерного анализа можно разделить на две
- 31. Иерархические агломеративные методы (Agglomerative Nesting, AGNES)Эта группа
- 32. Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)Эти
- 33. Слайд 33
- 34. Программная реализация алгоритмов кластерного анализа широко представлена
- 35. Иерархические алгоритмы связаны с построением дендрограмм (от
- 36. Существует много способов построения дендрограмм. В дендрограмме
- 37. Числа 11, 10, 3 и т.д. соответствуют
- 38. Методы объединения или связиКогда каждый объект представляет
- 39. Метод ближнего соседа или одиночная связь. Здесь
- 40. Слайд 40
- 41. Метод Варда (Ward's method). В качестве расстояния
- 42. Слайд 42
- 43. Метод наиболее удаленных соседей или полная связь.
- 44. Слайд 44
- 45. Метод невзвешенного попарного среднего (метод невзвешенного попарного
- 46. Метод взвешенного попарного среднего (метод взвешенного попарного
- 47. Невзвешенный центроидный метод (метод невзвешенного попарного центроидного
- 48. Слайд 48
- 49. Слайд 49
- 50. Важность алгоритмов “обучения без учителя” в том,
- 51. Дадим более строгую формулировку задачи обучения «без
- 52. где xij — значение j-ro признака для
- 53. При решении задачи обучения «без учителя» самыми
- 54. Алгоритм, основанный на понятии порогового расстоянияПороговый алгоритм
- 55. Самая первая точка-прототип может выбираться произвольно. Результатом
- 56. Алгоритм Выбрать точку-прототип первого класса (например, объект
- 57. Алгоритм 3. Определить пороговое расстояние Т = D(Z1,Z2)/2.Построить
- 58. Алгоритм
- 59. Рассмотрим пример работы алгоритма, основанного на вычислении
- 60. Выберем в качестве точки-прототипа первого класса точку
- 61. Наиболее удаленным объектом для Z1 будет Х8.
- 62. Слайд 62
- 63. Слайд 63
- 64. Слайд 64
- 65. Слайд 65
- 66. К достоинствам рассмотренного алгоритма следует отнести простоту
- 67. Из этого следует, что полезно было бы
- 68. Алгоритм MAXMINРассмотрим алгоритм, более эффективный по сравнению
- 69. Алгоритм MAXMINНа первом этапе алгоритма все объекты
- 70. В этом алгоритме пороговое расстояние не является
- 71. АлгоритмВыбрать точку-прототип первого класса (например, объект Х1
- 72. Алгоритм
- 73. Алгоритм
- 74. Рассмотрим работу алгоритма MAXMIN на примере. Как
- 75. Слайд 75
- 76. Скачать презентанцию
Человек, решающий задачу выбора целесообразного поведения в той или иной ситуации, прежде всего анализирует существенные и несущественные обстоятельства, влияющие на принимаемое решение. Процесс выделения существенных для данной задачи обстоятельств можно представить
Слайды и текст этой презентации
Слайд 3Оценка входной ситуации человеком происходит на основе совокупности сигналов, поступающих
от его органов чувств. На основании этих сигналов мозг вырабатывает
команды, которые обеспечивают реакцию человека на ситуацию. Сигналы поступают от рецепторов (зрительных, тактильных и др.). Совокупность таких сигналов формирует представление человека о ситуации.
Слайд 4Вычислительная машина, на которой моделируется аналогичный процесс, должна обладать возможностью
получать описание входной ситуации от внешних «рецепторов» в виде различных
наборов данных. Очевидно, объем информации, который получает компьютер, несоизмеримо меньше объемов информации, с которыми имеет дело человек; кроме того, такая информация будет представлена исключительно в численной форме.
Слайд 5Для того, чтобы эффективно оценить, относятся ли различные ситуации к
одному классу, интеллектуальная система должна иметь возможность рассмотреть и оценить
ряд конкретных примеров таких ситуаций, включенных в обучающее множество.
Слайд 6Обучение на основе примеров является типичным случаем индуктивного обучения и
широко используется в интеллектуальных системах. На основе предъявленных примеров (и,
возможно, контрпримеров) интеллектуальная система должна сформировать общее понятие, охватывающее примеры и исключающее контрпримеры.
Слайд 7Источником примеров, на которых осуществляется обучение, может быть учитель то
есть лицо, которое заранее знает концепцию формируемого понятия и подбирает
наиболее удачные обучающие выборки.
Слайд 8Источником примеров для обучения может быть внешняя среда, с которой
взаимодействует интеллектуальная система. В этом случае обучающие выборки формируются случайным
образом в зависимости от внешних факторов. Обучение на таких выборках существенно сложнее.
Слайд 9Наконец, источником примеров для обучения может стать сама интеллектуальная система.
Например, в случае взаимодействия интеллектуального робота с внешней средой действия
самого робота могут привести к созданию обучающей выборки, то есть образуется множество сходных ситуаций с известными результатами, которые можно затем обобщить.
Слайд 10Для системы машинного обучения принципиально важным является вопрос, что поступает
на вход системы, в каком виде предъявляются примеры понятия, включенные
в состав обучающего множества.Все основные методы решения задач индуктивного построения понятий базируются на концепции признакового описания примера понятия, а именно: любой элемент обучающей выборки, который может быть представлен в системе, полностью определяется набором свойств, или признаков. Такое задание объекта исследования называется признаковым описанием объекта.
Слайд 11Значения, которые могут принимать признаки объекта, относятся к трем основным
типам: количественные или числовые, качественные и шкалированные.
В случае числовых
признаков на множестве значений признаков может быть введена метрика, позволяющая дать количественную оценку значения признака. Часто такие значения являются результатом измерений физических величин, таких, как длина, вес, температура и др.
Слайд 12В случае, если признаки могут иметь качественный характер, но при
этом их значения можно упорядочить друг относительно друга, говорят, что
такие значения образуют ранговую или порядковую шкалу.Примерами таких шкал порядка могут быть ряды типа {большой, средний, маленький} или {горячий, теплый, холодный}. С помощью таких шкал порядка можно судить, какой из двух объектов является наилучшим, но нельзя оценить, сколь близки или далеки эти объекты по некоторому критерию.
Слайд 13Третий случай заключается в том, что значения признаков имеют чисто
качественный характер, связать эти значения между собой не удается. Примерами
таких значений могут быть цвет = {красный, желтый, зеленый} или материал = {стекло, дерево, пластмасса, железо}.
Слайд 16Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году,
включает в себя более 100 различных алгоритмов.
В отличие от задач
классификации, кластерный анализ не требует априорных предположений о наборе данных, не накладывает ограничения на представление исследуемых объектов, позволяет анализировать показатели различных типов данных (интервальным данным, частотам, бинарным данным). При этом необходимо помнить, что переменные должны измеряться в сравнимых шкалах.
Слайд 17Рассмотрим пример процедуры кластерного анализа.
Допустим, мы имеем набор данных А,
состоящий из 14-ти примеров, у которых имеется по два признака
X и Y. Данные по ним приведены в таблице.
Слайд 19Данные в табличной форме не носят информативный характер. Представим переменные
X и Y в виде диаграммы рассеивания
Слайд 20На рисунке мы видим несколько групп "похожих" примеров. Примеры (объекты),
которые по значениям X и Y "похожи" друг на друга,
принадлежат к одной группе (кластеру); объекты из разных кластеров не похожи друг на друга.Критерием для определения схожести и различия кластеров является расстояние между точками на диаграмме рассеивания. Это сходство можно "измерить", оно равно расстоянию между точками на графике. Способов определения меры расстояния между кластерами, называемой еще мерой близости, существует несколько.
Слайд 21
Наиболее распространенный способ - вычисление евклидова расстояния между двумя точками
i и j на плоскости, когда известны их координаты X
и Y:
Слайд 22Наиболее распространенный способ - вычисление евклидова расстояния между двумя точками
i и j на плоскости, когда известны их координаты X
и Y:Аналогично для трех координат
Слайд 23Кластер имеет следующие математические характеристики: центр, радиус, среднеквадратическое отклонение, размер
кластера.
Центр кластера - это среднее геометрическое место точек в пространстве
переменных.Радиус кластера - максимальное расстояние точек от центра кластера.
Кластеры могут быть перекрывающимися. Такая ситуация возникает, когда обнаруживается перекрытие кластеров. В этом случае невозможно при помощи математических процедур однозначно отнести объект к одному из двух кластеров. Такие объекты называют спорными.
Слайд 24Спорный объект - это объект, который по мере сходства может
быть отнесен к нескольким кластерам.
Размер кластера может быть определен либо
по радиусу кластера, либо по среднеквадратичному отклонению объектов для этого кластера. Объект относится к кластеру, если расстояние от объекта до центра кластера меньше радиуса кластера. Если это условие выполняется для двух и более кластеров, объект является спорным.Неоднозначность данной задачи может быть устранена экспертом или аналитиком.
Слайд 26Работа кластерного анализа опирается на два предположения. Первое предположение -
рассматриваемые признаки объекта в принципе допускают желательное разбиение пула (совокупности)
объектов на кластеры. В начале лекции мы уже упоминали о сравнимости шкал, это и есть второе предположение - правильность выбора масштаба или единиц измерения признаков.Выбор масштаба в кластерном анализе имеет большое значение.
Слайд 27Рассмотрим пример. Представим себе, что данные признака х в наборе
данных А на два порядка больше данных признака у: значения
переменной х находятся в диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1.Тогда, при расчете величины расстояния между точками, отражающими положение объектов в пространстве их свойств, переменная, имеющая большие значения, т.е. переменная х, будет практически полностью доминировать над переменной с малыми значениями, т.е. переменной у. Таким образом из-за неоднородности единиц измерения признаков становится невозможно корректно рассчитать расстояния между точками.
Слайд 28Эта проблема решается при помощи предварительной стандартизации переменных. Стандартизация (standardization)
или нормирование (normalization) приводит значения всех преобразованных переменных к единому
диапазону значений путем выражения через отношение этих значений к некой величине, отражающей определенные свойства конкретного признака. Существуют различные способы нормирования исходных данных.Наиболее распространенный:
деление исходных данных на среднеквадратичное отклонение соответствующих переменных
Слайд 29Наряду со стандартизацией переменных, существует вариант придания каждой из них
определенного коэффициента важности, или веса, который бы отражал значимость соответствующей
переменной. В качестве весов могут выступать экспертные оценки, полученные в ходе опроса экспертов - специалистов предметной области. Полученные произведения нормированных переменных на соответствующие веса позволяют получать расстояния между точками в многомерном пространстве с учетом неодинакового веса переменных
Слайд 30Методы кластерного анализа можно разделить на две группы:
иерархические;
неиерархические.
Суть
иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие
или разделении больших кластеров на меньшие
Слайд 31Иерархические агломеративные методы (Agglomerative Nesting, AGNES)
Эта группа методов характеризуется последовательным
объединением исходных элементов и соответствующим уменьшением числа кластеров.
В начале работы
алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.
Слайд 32Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)
Эти методы являются логической
противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат
одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.
Слайд 34Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах
Data Mining, которые позволяют решать задачи достаточно большой размерности. Например,
агломеративные методы реализованы в пакете SPSS, дивизимные методы - в пакете Statgraf.Иерархические методы кластеризации различаются правилами построения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о "схожести" объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).
Иерархические методы кластерного анализа используются при небольших объемах наборов данных.
Преимуществом иерархических методов кластеризации является их наглядность.
Слайд 35Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron -
"дерево"), которые являются результатом иерархического кластерного анализа.
Дендрограмма описывает близость
отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров. 
Слайд 36Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться
вертикально или горизонтально. Пример вертикальной дендрограммы
Слайд 37Числа 11, 10, 3 и т.д. соответствуют номерам объектов или
наблюдений исходной выборки. Мы видим, что на первом шаге каждое
наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.
Слайд 38Методы объединения или связи
Когда каждый объект представляет собой отдельный кластер,
расстояния между этими объектами определяются выбранной мерой. Возникает следующий вопрос
- как определить расстояния между кластерами? Существуют различные правила, называемые методами объединения или связи для двух кластеров.
Слайд 39Метод ближнего соседа или одиночная связь. Здесь расстояние между двумя
кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями)
в различных кластерах. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов.В результате работы этого метода кластеры представляются длинными "цепочками" или "волокнистыми" кластерами, "сцепленными вместе" только отдельными элементами, которые случайно оказались ближе остальных друг к другу.
Слайд 41Метод Варда (Ward's method). В качестве расстояния между кластерами берется
прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в
результате их объединения (Ward, 1963). В отличие от других методов кластерного анализа для оценки расстояний между кластерами, здесь используются методы дисперсионного анализа. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров и "стремится" создавать кластеры малого размера.
Слайд 43Метод наиболее удаленных соседей или полная связь. Здесь расстояния между
кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных
кластерах (т.е. "наиболее удаленными соседями"). Метод хорошо использовать, когда объекты действительно происходят из различных "рощ". Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является "цепочечным", то этот метод не следует использовать.
Слайд 45Метод невзвешенного попарного среднего (метод невзвешенного попарного арифметического среднего -
unweighted pair-group method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)).
В
качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Этот метод следует использовать, если объекты действительно происходят из различных "рощ", в случаях присутствия кластеров "цепочного" типа, при предположении неравных размеров кластеров.
Слайд 46Метод взвешенного попарного среднего (метод взвешенного попарного арифметического среднего -
weighted pair-group method using arithmetic averages, WPGM A (Sneath, Sokal,
1973)). Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере).Этот метод рекомендуется использовать именно при наличии предположения о кластерах разных размеров.
Слайд 47Невзвешенный центроидный метод (метод невзвешенного попарного центроидного усреднения - unweighted
pair-group method using the centroid average (Sneath and Sokal, 1973)).
В
качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.
Слайд 50Важность алгоритмов “обучения без учителя” в том, что реальные признаки,
описывающие объекты распознавания, очень часто бывают именно количественными, или числовыми.
Известно, что человек плохо воспринимает информацию, представленную в виде больших наборов чисел. Первым и крайне важным этапом решения задачи обобщения в таком случае будет переход от количественных признаков к признакам качественным или хотя бы к шкалируемым. Здесь большую помощь могут оказать алгоритмы рассматриваемого типа.
Слайд 51Дадим более строгую формулировку задачи обучения «без учителя».
Пусть обучающая выборка
содержит М объектов: X = {X1,X2,…,Хn}- Каждый из этих объектов
представляет собой n-мерный вектор Xi значений признаков:
Слайд 52
где xij — значение j-ro признака для i-го объекта, п
— количество признаков, характеризующих объект.
Признаки, используемые для описания объекта, чисто
количественные, к ним применимы введенные в предыдущей главе меры близости.Требуется в соответствии с заданным критерием разделить набор X на классы, количество которых заранее неизвестно. Под критерием подразумевается мера близости всех объектов одного класса между собой. Будем считать, что работа алгоритма завершена успешно, если классы, сформированные в результате работы алгоритма, достаточно компактны и, возможно, выполнены некоторые дополнительные критерии.
Слайд 53При решении задачи обучения «без учителя» самыми несложными являются алгоритмы,
основанные на мерах близости. Для достижения цели - компактного формирования
классов — введем понятие точки-прототипа, или точки в n-мерном пространстве признаков, являющейся наиболее «типичной» представительницей построенного класса. В дальнейшем расстояние от объекта до класса будет заменяться расстоянием от объекта до точки-прототипа. Точка-прототип может быть сопоставлена каждому сформированному классу, и при этом вовсе не обязательно существование реального объекта, соответствующего точке-прототипу.
Слайд 54Алгоритм, основанный на понятии порогового расстояния
Пороговый алгоритм — один из
самых несложных алгоритмов, базирующихся на понятии меры близости. Критерием отнесения
объекта к классу здесь является пороговое расстояние Т. Если объект находится в пределах порогового расстояния от точки-прототипа некоторого класса, то такой объект будет отнесен к данному классу. Если исследуемый объект находится на расстоянии, превышающем Т, он становится прототипом нового класса.
Слайд 55Самая первая точка-прототип может выбираться произвольно. Результатом работы такого алгоритма
будет разбиение объектов выборки X на классы, где в каждом
классе расстояние между точкой-прототипом и любым другим элементом класса не превышает Т. Пороговое расстояние Т определим как половину расстояния между двумя наиболее удаленными друг от друга точками обучающей выборки.
Слайд 56Алгоритм
Выбрать точку-прототип первого класса (например, объект Х1 из обучающей
выборки). Количество классов К положить равным 1. Обозначить точку-прототип Z1.
Определить
наиболее удаленный от Z1 объект Xf по условиюD(Z1,Xf) = max D(Z1, Xi),
где D(Z1,Xf) - расстояние между Z1 и Xf, вычисленное одним из возможных способов. Объявить Xf прототипом второго класса. Обозначить Xf как Z2. Число классов К = К + 1.
Слайд 59
Рассмотрим пример работы алгоритма, основанного на вычислении порогового расстояния. Пусть
каждый объект из множества объектов, представленных в таблице, задан двумя
признаками (модель - точка на плоскости)
Слайд 60Выберем в качестве точки-прототипа первого класса точку Х1 из обучающей
выборки (обозначается далее Z1). В таблице представлены расстояния от этой
точки до объектов Х2 — Х8.
Слайд 61Наиболее удаленным объектом для Z1 будет Х8.
Пороговое расстояние
Точка Х8
становится точкой-прототипом второго класса и обозначается далее Z2.
Рассматриваем точки
множества
Слайд 66К достоинствам рассмотренного алгоритма следует отнести простоту реализации и небольшой
объем вычислений.
Недостатки:
не предусмотрено уточнение разбиения. В результате расстояние
от объекта до точки-прототипа класса может оказаться больше, чем расстояние от этого объекта до точки-прототипа другого класса. Результат, кроме того, сильно зависит от порядка рассмотрения объектов X, а также от способа вычисления порогового расстояния (можно использовать и другие формулы для подсчета Т).
Слайд 67Из этого следует, что полезно было бы использовать алгоритмы, допускающие
многократную коррекцию формируемых классов, например, можно было бы менять пороговое
расстояние Т и проводить многократное уточнение разбиения.
Слайд 68Алгоритм MAXMIN
Рассмотрим алгоритм, более эффективный по сравнению с предыдущим и
являющийся улучшением порогового алгоритма. Исходными даннымы для работы алгоритма будет,
как и раньше, выборка X. Объекты этой выборки следует разделить на классы, число и характеристики которых заранее неизвестны.
Слайд 69Алгоритм MAXMIN
На первом этапе алгоритма все объекты разделяются по классам
на основе критерия минимального расстояния от точек-прототипов этих классов (первая
точка-прототип может выбираться произвольо). Затем в каждом классе выбирается объект, наиболее удаленный от своего прототипа. Если он удален от своего прототипа на расстояние, превышающее пороговое, такой объект становится прототипом нового класса.
Слайд 70В этом алгоритме пороговое расстояние не является фиксированным, а определяется
на основе среднего расстояния между всеми точками-прототипами, то есть корректируется
в процессе работы алгоритма. Если в ходе распределения объектов выборки X по классам были созданы новые прототипы, процесс распределения повторяется. Таким образом, в алгоритме MAXMIN окончательным считается разбиение, для которого в каждом классе расстояние от точки-прототипа до всех объектов этого класса не превышает финального значения порога Т.
Слайд 71Алгоритм
Выбрать точку-прототип первого класса (например, объект Х1 из обучающей выборки).
Количество классов К положить равным 1. Обозначить точку-прототип Z1.
Определить наиболее
удаленный от Z1 объект Xf по условиюD(Z1,Xf) = max D(Z1, Xi),
где D(Z1,Xf) - расстояние между Z1 и Xf, вычисленное одним из возможных способов. Объявить Xf прототипом второго класса. Обозначить Xf как Z2. Число классов К = К + 1.
Слайд 74Рассмотрим работу алгоритма MAXMIN на примере. Как и в предыдущем
случае выберем объекты, которые заданы двумя признаками. Обучающая выборка представлена
на рис.
