Достоинства и недостатки методов, основанных на близости описании.

+: Простота реализации

-: Необх хранения всей обуч послед-и. Отсутствие гарантии привильного распознавания, невозможность оценки качества РП

IV.Обучение без учителя

19. Меры сходства изображений, используемые для выявления классов (кластеров).

В качестве меры между образами x и z можно использовать:

1. Евклидово расстояние: .

2. косинус угла между векторами,

3. Мера Танимото - отношение количества совпадающих к количеству различных признаков двух образов.

20. Подходы к построению процедуры классификации (кластеризации).

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

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

где — число кластеров, — множество образов, относящихся к j-му кластеру, а —вектор выборочных средних значений для множества Sj; Ni характеризует количество образов, входящих во множество Sj.

21. Простой эвристический алгоритм определения кластеров.

Шаг 0. Пусть задано множество N образов X₁, …, X_N. Пусть центр первого кластера z₁ совпадает с любым из заданных образов и определена произвольная неотрицательная пороговая величина t.

Шаг 1. Вычисляется расстояние D₂₁ между образом X₂ и центром кластера z₁ по формуле евклидового расстояния. Если D₂₁> t, то учреждается новый центр кластера z₂=X₂. В противном случае образ X₂ включается в кластер c центром z₁.

Шаг 3. Вычисляются расстояния D₃₁ и D₃₂ от образа X₃ до центров кластеров z₁ и z₂. Если D₃₁> t и D₃₂> t, то учреждается новый центр кластера z₃=X₃. В противном случае образ X₃ зачисляется в тот кластер, чей центр к нему ближе.

Шаг m. Подобным же образом расстояния от каждого нового образа до каждого известного центра кластера вычисляются и сравниваются с пороговой величиной—если все эти расстояния превосходят значение порога t, учреждается новый центр кластера. В противном случае образ зачисляется в кластер с самым близким к нему центром.

Эвристический алгоритм максиминного расстояния.

Шаг 0. Пусть задано множество N образов X₁, …, X_N.

Шаг 1. Один из заданных образов назначается центром первого кластера z₁. Возьмем z₁=X₁.

Шаг 2. Затем отыскивается образ, отстоящий от образа X₁ на наибольшее расстояние. Он назначается центром кластера z₂.

Шаг 3. Вычисляются расстояния между всеми остальными образами выборки и центрами кластеров z₁ и z₂. В каждой паре этих расстояний выделяется минимальное. После этого выделяется максимальное из этих минимальных расстояний. Если последнее составляет значительную часть расстояния между центрами кластеров z₁ и z₂ соответствующий образ назначается центром кластера z₃. В противном случае выполнение алгоритма прекращается.

Шаг m. В общем случае подобная процедура повторяется до тех пор, пока на каком-либо шаге не будет получено максимальное расстояние, для которого условие, определяющее выделение нового кластера, не выполняется.

 

Алгоритм К внутригрупповых средних.

1 шаг. Выбираются К исходных центров кластеров

z₁(1), z₂(1), z₃(1), …, z_k(1) Обычно берутся первые К точек

2 шаг. На К-ом шаге итерации заданное мн-во Х распределяется по К кластерам след. образом xÎ S_j(k) если ||x-z_j(k)||< =||x-z_i(k)|| i=1…k i< > j

3 шаг. На основании результата 2шага выбираются новые центры кластеров z(k+1) исходя из того, что расстояние между всеми образами в S_j(k) и новым центром будет минимально.

4 шаг. Если z_j(k+1)=z(k), то алгоритм останавливается Иначе происходит новое разбиение и алгоритм продолжается до тех пор пока не будет найден оптимальное решение.

 

Алгоритм ISODATA.

Общая структура алгоритма такова:

1. Формирование подмножеств выборочных множеств .

2. Слияние кластеров (если требуется с переходом на 1).

3. Расщепление кластеров (если требуется с переходом на 1).

При этом используются следующие эвристики:

1. Ликвидация кластеров с числом элементов меньше заданного значения.

2. Объединение кластеров, находящихся близко друг к другу.

При объединении кластеров с центрами и образуется один кластер с центром

Расщепление кластера может происходить по одному из следующих критериев:

1. При достаточно сильной разбросанности образов расщепляемого кластера в масштабе общего множества образов.

2. Если требуется получить достаточно большое число кластеров.

 

⇐ Предыдущая123Следующая ⇒

Поделиться:

Популярное:

1. БОЛЕЗНИ, ДЕФЕКТЫ И НЕДОСТАТКИ ВИН
2. В которой описываются неоспоримые достоинства поездов как новейшего, удобнейшего и наиболее безопасного средства передвижения
3. Вопрос 84. Защита чести, достоинства, деловой репутации. Распределение бремени доказывания. Защита чести, достоинства и деловой репутации (ст. 152 ГК)
4. Глава 17. Преступления против свободы, чести и достоинства личности
5. Глава VI. ПРЕСТУПЛЕНИЯ ПРОТИВ ЖИЗНИ, ЗДОРОВЬЯ, СВОБОДЫ И ДОСТОИНСТВА ЛИЧНОСТИ
6. ДОСТОИНСТВА БЛАГОТВОРИТЕЛЬНОСТИ
7. Достоинства имамов (да будет над ними мир)
8. Каскадная и спиральная модели жизненного цикла ПО. Преимущества, недостатки, применимость.
9. Мажоритарная избирательная система: ее основные характеристики, преимущества и недостатки. Избирательная система РБ.
10. Методики расчета технически обоснованных норм труда.
11. Методы оценки качества продукции, их достоинства и недостатки.