_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185318), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Рис.18. Общая схема комитетного синтеза коллективных кластеризаций

Вопрос выбора исходного набора алгоритмов кластеризации является в значительной мере «открытым» и здесь естественны различные подходы.

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

Другой подход к выбору базисного набора коллективных кластеризаций состоит в использовании набора различных кластеризаций, полученных в рамках одного подхода. Например, это могут быть кластеризации, соответствующие различным локально- оптимальным разбиениям по некоторому критерию качества разбиений (например, сумме квадратов дисперсий).

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

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

Для применения метода синтеза оптимальных коллективных решений в случаях различного числа кластеров полученных исходными алгоритмами, каждое исходное решение преобразуется к решению на кластеров, например, с помощью объединения «ближайших» кластеров в один, или «дублирования» некоторых классов (создания равных столбцов в соответствующих матрицах ).

Глава 3. Алгоритмы распознавания и интеллектуального анализа данных в системе РАСПРОЗНАВАНИЕ

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

3.1. Алгоритмы вычисления оценок

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

Для вычисления оценок используются формулы (1.16) или (1.17). Значения числовых параметров задают пороги близости соответствующих признаков и вычисляются как средний модуль разности значений признака по обучающей выборке: .

Для классификации применяется общее линейное решающее правило (1.14), неизвестные значения параметров которого находятся в результате решения задачи оптимизации модели. В данном случае решается задача поиска максимальной совместной подсистемы системы линейных неравенств с помощью релаксационного метода /46/(см. раздел 3.5).

3.2. Голосование по тупиковым тестам

В Системе РАСПОЗНАВАНИЕ реализован один стохастический вариант тестового алгоритма. Из таблицы обучения выбираются случайно N подтаблиц, каждая из которых состоит из 3 строк таблицы обучения, N подтаблиц, состоящих из 4 строк таблицы обучения, и т.д., N подтаблиц, состоящих из k строк таблицы обучения (здесь N и k – управляющие параметры программы). Каждая подтаблица не обязана содержать эталоны из каждого класса, т.е. допускаются подтаблицы с числом строк меньшим числа классов. Каждому тесту выбранной подтаблицы сопоставляется вес (качество), оцененный уже по полной обучающей выборке. Для каждой подтаблицы находятся все тупиковые тесты либо один минимальный тест в зависимости от выбранного алгоритма поиска. В последнем случае для таблицы обучения находится не более N(k-2) минимальных тестов случайных подтаблиц.

Обозначим множество всех найденных тупиковых тестов для подтаблиц, как и ранее, через . Пусть M₁ ={ , } множество пар строк таблицы обучения, принадлежащих равным классам, а M₂ - множество пар строк из разных классов. Число элементов множеств M₁ и M₂ обозначим, соответственно, через n₁ и n₂. Антиблизость объектов по опорному множеству определяется как .

Определим «вес» опорного множества (в нашем случае теста T) согласно выражению (3.1)

_{, (3.1)}

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

Окончательно, оценки распознаваемого объекта за классы , j=1,2,…,l, вычисляются согласно следующей формуле:

_.

_{Классификация осуществляется с помощью простейшего решающего правила.}

_{В случаях практических задач с плохой отделимостью классов тупиковые тесты будут иметь большое число столбцов или могут вообще отсутствовать. Для «управления отделимостью классов» введен управляющий параметр программы (делитель  - порогов), позволяющий увеличивать-уменьшать близость объектов. Для таблиц обучения с небольшим числом признаков возможно вычисление всех тупиковых тестов и, соответственно, голосование по всем тупиковым тестам. Для реализации данного варианта в Системе предусмотрена кнопка «переборный алгоритм».}

1. Алгоритмы голосования по логическим закономерностям классов

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

(3.2)

(или конъюнкции (3.2), соответствующие некоторому подмножеству признаков) такие, что:

1. хотя бы для одного объекта обучающей выборки выполнено

2. для любого объекта обучающей выборки выполнено ;

3. доставляет экстремум некоторому критерию качества где - множество всевозможных предикатов (3.2), удовлетворяющих условиям 1), 2) /71, 76/.

В системе РАСПОЗНАВАНИЕ рассматривается стандартный критерий качества: «число эталонов из класса : »/ .

Логическая закономерность класса называется частичной, если выполнены пункты 1), 3), а требование 2) заменяется более слабым 2:

(доля объектов «чужих» классов, для которых выполнено , не превышает заданный порог).

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

В случае вещественнозначных признаков, логической закономерности (3.2) соответствует простая геометрическая интерпретация: в некотором признаковом подпространстве имеется гиперпараллелепипед, содержащий максимальное число объектов обучения из класса и только класса . Логические закономерности являются аналогом представительных наборов для случаев бинарных и k-значных признаков /3, 10, 22/. Другие близкие понятия рассматривались в /35/ и в многочисленных публикациям по решающим деревьям (например, /16, 17/).

Алгоритм поиска множества логических закономерностей класса состоит в решении последовательности однотипных «отмеченных» задач. Число данных задач определяется автоматически согласно предполагаемому существованию , для которого стандартный критерий качества  h (h – параметр программы, именуемый как «минимальная доля объектов»). Опишем подобную «отмеченную» задачу.

Характеристики

Список файлов книги