Алгоритмы обучения без учителя

Содержание

Слайд 2

Алгоритм MAXMIN Рассмотрим алгоритм, более эффективный по сравнению с предыдущим и

Алгоритм MAXMIN
Рассмотрим алгоритм, более эффективный по сравнению с предыдущим и являющийся

улучшением порогового алгоритма. Исходными даннымы для работы алгоритма будет, как и раньше, выборка X. Объекты этой выборки следует разделить на классы, число и характеристики которых заранее неизвестны.
Слайд 3

Алгоритм MAXMIN На первом этапе алгоритма все объекты разделяются по классам

Алгоритм MAXMIN
На первом этапе алгоритма все объекты разделяются по классам на

основе критерия минимального расстояния от точек-прототипов этих классов (первая точка-прототип может выбираться произволь­о). Затем в каждом классе выбирается объект, наиболее удаленный от своего прототипа. Если он удален от своего прототипа на расстояние, превышающее пороговое, такой объект становится прототипом нового класса.
Слайд 4

В этом алгоритме пороговое расстояние не является фиксированным, а определяется на

В этом алгоритме пороговое расстояние не является фиксированным, а определяется на

основе среднего расстояния между всеми точками-прототипами, то есть корректируется в процессе работы алгоритма. Если в ходе распределения объектов выборки X по классам были созданы новые прототипы, процесс распределения повторяется. Таким образом, в алгоритме MAXMIN окончательным считается разбиение, для которого в каждом классе расстояние от точки-прототипа до всех объектов этого класса не превышает финального значения порога Т.
Слайд 5

Алгоритм Выбрать точку-прототип первого класса (например, объект Х1 из обучающей выборки).

Алгоритм
Выбрать точку-прототип первого класса (например, объект Х1 из обучающей выборки). Количество

классов К положить равным 1. Обозначить точку-прототип Z1.
Определить наиболее удаленный от Z1 объект Xf по условию
D(Z1,Xf) = max D(Z1, Xi),
где D(Z1,Xf) - расстояние между Z1 и Xf, вычисленное одним из возможных способов. Объявить Xf прототипом второго класса. Обозначить Xf как Z2. Число классов К = К + 1.
Слайд 6

Алгоритм

Алгоритм

Слайд 7

Алгоритм

Алгоритм

Слайд 8

Рассмотрим работу алгоритма MAXMIN на примере. Как и в предыдущем случае

Рассмотрим работу алгоритма MAXMIN на примере. Как и в предыдущем случае

выберем объекты, которые заданы двумя признаками. Обучающая выборка представлена на рис.
Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Слайд 17

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Слайд 22

Слайд 23

Слайд 24

Слайд 25

Слайд 26

Слайд 27

Слайд 28

Проблемы алгоритма K-средних: необходимо заранее знать количество кластеров. алгоритм очень чувствителен

Проблемы алгоритма K-средних:
необходимо заранее знать количество кластеров.
алгоритм очень чувствителен к

выбору начальных центров кластеров. Классический вариант подразумевает случайный выбор кластеров, что очень часто являлось источником погрешности. Как вариант решения, необходимо проводить исследования объекта для более точного определения центров начальных кластеров.
не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному.
Слайд 29

Слайд 30

Слайд 31

Нечеткий алгоритм кластеризации с-means С последней проблемой k-means успешно справляется алгоритм

Нечеткий алгоритм кластеризации с-means
С последней проблемой k-means успешно справляется алгоритм

с-means. Вместо однозначного ответа на вопрос к какому кластеру относится объект, он определяет вероятность того, что объект принадлежит к тому или иному кластеру. Таким образом, утверждение «объект А принадлежит к кластеру 1 с вероятностью 90%, к кластеру 2 — 10% » верно и более удобно.
Классический пример с-means — т.н. «бабочка» (butterfly):
Слайд 32

Слайд 33

Алгоритм ISODATA (Iterative Self-Organizing Data Analysis Techniques) основывается на алгоритме k

Алгоритм ISODATA (Iterative Self-Organizing Data Analysis Techniques) основывается на алгоритме k

средних, но включает набор оказавшихся полезными на практике эвристик и параметры по их настройке. Одним из задаваемых априори параметров является желаемое число кластеров K.
Слайд 34

Это число выступает в качестве рекомендации: в результате работы алгоритма может

Это число выступает в качестве рекомендации: в результате работы алгоритма может

быть построено как меньшее, так и большее число кластеров, но оно будет не сильно отличаться от значения K. Сам алгоритм здесь детально описываться не будет (в целом, в нем используются те же шаги, что и в алгоритме k средних); приведем лишь основные эвристики.
Слайд 35

Ликвидируются кластеры, в состав которых входит менее чем заданное число элементов.

Ликвидируются кластеры, в состав которых входит менее чем заданное число элементов.
Для

каждого текущего кластера определяется направление максимальной вытянутости. Наиболее вытянутый кластер может быть расщеплен на два.
Слайд 36

Решение о расщеплении принимается с учетом размера кластера в направлении вытянутости

Решение о расщеплении принимается с учетом размера кластера в направлении вытянутости

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

Слайд 38

Использующиеся в алгоритме ISODATA эвристики помогают не только подбирать более подходящее

Использующиеся в алгоритме ISODATA эвристики помогают не только подбирать более подходящее

число классов, но и находить более приемлемое решение, несколько ослабляя (но не убирая полностью) зависимость от начальной гипотезы.
Слайд 39

Слайд 40

Слайд 41

Слайд 42

Слайд 43

Слайд 44

Слайд 45

Слайд 46

Слайд 47

Слайд 48

Слайд 49

Слайд 50

Слайд 51

Слайд 52

Слайд 53

Слайд 54

Слайд 55

Слайд 56

Задача минимизации количества решающих функций, достаточных для классификации образов, может быть

Задача минимизации количества решающих функций, достаточных для классификации образов, может быть

очень важна, особенно если количество классов d велико. Если представить себе, с каким количеством классов объектов (или понятий) имеет дело человек, становится ясно, что решение этой проблемы в том или ином виде потребуется при разработке универсальной системы машинного обучения. Мы, однако, этот вопрос здесь рассматривать не будем, а перейдем к проблеме распознавания образов.
Слайд 57

Слайд 58

Слайд 59

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

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

на основе неких эвристических соображений. Два наиболее широко распространенных эвристических метода – это метод эталонных образов и метод ближайшего соседа.
Метод эталонных образов
Метод эталонных образов – это один из эвристических методов построения решающих правил. В основу этого метода положена идея, которая заключается в том, что некоторая совокупность объектов, объединенных в отдельный класс, может быть представлена одним или несколькими эталонными объектами.
Слайд 60

Эти эталонные объекты являются наиболее типичными представителями класса. Типичность эталонного объекта

Эти эталонные объекты являются наиболее типичными представителями класса. Типичность эталонного объекта

означает, что он в среднем максимально похож на все объекты класса.
Поскольку сходство двух объектов может трактоваться как величина, противоположная расстоянию между ними в пространстве описаний (образов), то эталон – это объект, для которого минимально среднее расстояние до других объектов.
Слайд 61

Слайд 62

Классы, однако, могут обладать разными свойствами. Простейшим свойством является характерный размер

Классы, однако, могут обладать разными свойствами. Простейшим свойством является характерный размер

класса, который может быть оценен как
Слайд 63

Слайд 64

Слайд 65

В соответствии с данным решающим правилом просматривается вся обучающая выборка, в

В соответствии с данным решающим правилом просматривается вся обучающая выборка, в

ней находится образ, расположенный наиболее близко к данному и устанавливается, к какому классу он принадлежит (это известно, поскольку он находится в обучающей выборке). Этот класс и приписывается новому образу.
Слайд 66

Метод ближайшего соседа весьма чувствителен к выбросам, то есть тем образам

Метод ближайшего соседа весьма чувствителен к выбросам, то есть тем образам

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

Слайд 68

Слайд 69

Слайд 70

Слайд 71

Слайд 72

Слайд 73

Слайд 74

Слайд 75

Слайд 76

Слайд 77

Слайд 78

Слайд 79

Слайд 80

Слайд 81

Слайд 82

Слайд 83

Слайд 84