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

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

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

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

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

Сначалапользователь просматривает проекции выборки на различные плоскости пар признаков ивыделяет кластеры объектов на тех проекциях, где просматриваются некоторые сгущенияили группировки. Далее, полученный набор плоских решений используется в качествеисходного множества кластеризаций для построения коллективного решения. Такимобразом, решение задачи кластерного анализа находится в результате комитетногосинтеза набора точных кластеризаций, полученных по различным частям обрабатываемойвыборки /79/.Для применения метода синтеза оптимальных коллективных решений в случаяхразличного числа кластеров полученных исходными алгоритмами, каждое исходноерешение преобразуется к решению на l кластеров, например, с помощью объединения«ближайших» кластеров в один, или «дублирования» некоторых классов (созданияравных столбцов в соответствующих матрицах I ).67Глава 3.

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

Алгоритмы вычисления оценокОптимальные значения параметров алгоритмов распознавания, основанных навычислении оценок, определяются из решения задачи оптимизации данной моделираспознавания - находятся такие значения параметров, при которых точностьраспознавания на обучающей выборке является максимальной.Для вычисления оценок используются формулы (1.16) или (1.17). Значениячисловых параметров (1 ,  2 , . . .

,  n ) задают пороги близости соответствующих признакови вычисляются как средний модуль разности значений признака по обучающей выборке: m2| x ( S i )  x ( S j ) | .m(m  1) i , j 1,i  jДля классификации применяется общее линейное решающее правило (1.14),неизвестные значения параметров которого находятся в результате решения задачиоптимизации модели.

В данном случае решается задача поиска максимальной совместнойподсистемы системы линейных неравенств с помощью релаксационного метода /46/(см.раздел 3.5).3.2. Голосование по тупиковым тестамВ Системе РАСПОЗНАВАНИЕ реализован один стохастический вариант тестовогоалгоритма.

Из таблицы обучения выбираются случайно N подтаблиц, каждая из которыхсостоит из 3 строк таблицы обучения, N подтаблиц,состоящих из 4 строк таблицыобучения, и т.д., N подтаблиц, состоящих из k строк таблицы обучения (здесь N и k –управляющие параметры программы). Каждая подтаблица не обязана содержать эталоныиз каждого класса, т.е. допускаются подтаблицы с числом строк меньшим числа классов.Каждому тесту выбранной подтаблицы сопоставляется вес (качество), оцененный уже по68полной обучающей выборке. Для каждой подтаблицы находятся все тупиковые тестылибо один минимальный тест в зависимости от выбранного алгоритма поиска.

Впоследнем случае для таблицы обучения находится не более N(k-2) минимальных тестовслучайных подтаблиц.Обозначим множество всех найденных тупиковых тестов для подтаблиц, как иранее, через {T } . Пусть M1 ={ Si , S j } множество пар строк таблицы обучения,принадлежащих равным классам, а M2 - множество пар строк из разных классов. Числоэлементов множеств M1 и M2 обозначим, соответственно, через n1 и n2. Антиблизостьобъектов по опорному множеству T  {T } определяется как DT ( S , S  )  1  BT ( S , S  ) .Определим «вес» опорного множества (в нашем случае теста T) согласновыражению (3.1)QT 11DT Si , S j   DT Si , S j n2 S i , S j M 2n1 S i , S j M 1а через wT ,(3.1)QT– его удельный вес.

Данные величины показывают, как часто бывают QTT {T }близки эталонные объекты одного класса и далеки объекты разных классов повыбранному опорному множеству.Окончательно, оценки распознаваемого объекта за классыK j , j=1,2,…,l,вычисляются согласно следующей формуле: j (S ) 1wT  K j2 T {T } 1BSi K jT(S , Si )  m  K j  D (S , S ) 1Si K jTi.Классификация осуществляется с помощью простейшего решающего правила.В случаях практических задач с плохой отделимостью классов тупиковые тесты будутиметь большое число столбцов или могут вообще отсутствовать.

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

Подлогическими закономерностями класса K j в данном случае понимаются предикаты видаP( S )  (a1  x1 ( S )  b1 ) & (a2  x2 ( S )  b2 ) & ... & (an  xn ( S )  bn )  {0,1}(3.2)(или конъюнкции (3.2), соответствующие некоторому подмножеству признаков) такие,что:1) хотя бы для одного объекта обучающей выборки S i  K j выполненоP( S i )  1;2) для любого объекта S i обучающей выборки Si  K j выполнено P( S i )  0 ;доставляет3) P (S )экстремумнекоторомукритериюкачества ( P)  extr  ( P' ), где  - множество всевозможных предикатов (3.2), удовлетворяющихP 'условиям 1), 2) /71, 76/.В системе РАСПОЗНАВАНИЕ рассматривается стандартный критерий качества: (P )  «число эталонов S i из класса K j : P( S i )  1 »/ K j .Логическая закономерность класса K j называется частичной, если выполнены пункты 1),3), а требование 2) заменяется более слабым 2:Si K j | PS i   1{PS i   1}(доля объектов «чужих» классов, для которых выполненоP( S i )  1 , не превышает заданный порог).Поскольку задача оптимизации  (P ) обычно многоэкстремальна, логическимизакономерностями класса считаются все предикаты P (S ) , доставляющие локальныйэкстремум критерию  (P ) .В случае вещественнозначных признаков, логической закономерности (3.2)соответствует простая геометрическая интерпретация: в некотором признаковомподпространстве имеется гиперпараллелепипед, содержащий максимальное числообъектов обучения из класса K j и только класса K j .

Логические закономерностиявляются аналогом представительных наборов для случаев бинарных и k-значныхпризнаков /3, 10, 22/. Другие близкие понятия рассматривались в /35/ и в многочисленныхпубликациям по решающим деревьям (например, /16, 17/).Алгоритм поиска множества логических закономерностей класса состоит врешении последовательности однотипных «отмеченных» задач. Число данных задач70определяется автоматически согласно предполагаемому существованиюP (S ) , длякоторого стандартный критерий качества  (P )  h (h – параметр программы, именуемыйкак «минимальная доля объектов»).

Опишем подобную «отмеченную» задачу.Пусть Si  K j - случайно выбранный объект таблицы обучения (будем называтьего «опорный» эталон). В работе /77/ описан метод поиска множества логическихзакономерностей P (S ) класса K j таких, что P( S i )  1 . Поиск оптимального предикатаP (S )для опорного эталона S i(т.е. значений параметров a1 , a 2 ,..., a n , b1 , b2 ,..., bn )осуществляется сначала на некоторой неравномерной сетке пространства R n , котораязадается числом интервалов разбиения значений каждого признака (для некоторыхпризнаков, например k-значных, в реальности число интервалов будет меньше заданного).После нахождения оптимального предиката P (S ) на заданной сетке, происходит поископтимального предиката P (S ) на более мелкой сетке, в окрестности ранее найденногоP (S ) , и т.д.

Процесс оптимизации заканчивается и задача поиска множества логическихзакономерностей, связанных с заданным опорным объектом считается решенной, если припереходе к более мелкой сетке не удается найти предикат P (S ) с более высокимзначением критерия качества  (P ) .xkSixjxiРис.19. Геометрическая интерпретация логической закономерности класса. Символами «звездочка»отмечены объекты класса, для которого вычисляются логические закономерностями, символами «круг» эталонные объекты остальных классовЗадача поиска оптимального P (S ) на каждой сетке состоит в поиске максимальнойсовместной подсистемы некоторой системы неравенств, при линейных ограничениях71относительно бинарных переменных, и некоторого ее решения.

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

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