Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 55
Текст из файла (страница 55)
В этой главе мы рассмотрим задачу классификацп»г объектов без использования обучающего множества. Назовем этот вид классификации автоматической классификацией ил1х классификацией без учителя. Существует много примеров, когда классификация должна рной информации. и может быть выполнена при отсутствии априорно ф Рассмотрим, например, задачу биологической таксономии, Па протяжении многих лет все известные живые организмы классифицировались в соответствии с определенными наблюдаемыми характеристиками. Конечно растения и животнь ь ные не родятся с ярлыками, указывающими их семейство тип и ..
О и т. д. ни классифицируются в соответствии с их наблюдаемыми характерпстикамп без указаний извне. стью опрелеЗадача автоматической классификации не полностью лена, если не указаны свойства, которыми должны обладать искомые классы объектов. Выбор этих свойств пли, плп, что то же, определение класса — это основной вопрос теории автоматической классификации. Если имеется адекватное определение класса, становится возможным отличать хорошие класс~ ф кл ссификации ог плохих. В нашем примере классы образуются объединением в о~ну группу похожих видов и разделением непохожих. Группировка по сходству является наиболее общей формой ' автоматической классификации, и мы ее подробно рассмотрим. Однако, как удет показано в конце этой главы, автоматическая классификация возможна и на базе более общих отношений между объектами.
Для того чтобы построить автоматическую процедуру решения задачи автоматической классификации, необходимо дать более строгое определение класса. Один из возможных путей— это конструирование критерия качества классификации. Критерий качества классификации 1 ставит в соответствие каждой возможной классификации множества объектов некоторое число. Областью определения 1 является множество всех Возможных классификаций объектов, а областью значений — множество действительных чисел. Предполагается, что классификации, хорошие в смысле принятого определения класса, соответствуют экстремальным значениям критерия 1. Таким образом, если критерий 1 задан, то можно оценить любую данную классификацию. Как правило, однако, нереально вычислять 1 для каждой возможной классификации.
Поэтому для эффективного определения наилучшей в смысле критерия 1 классификации необходим алгоритм автоматической классифика.ции. В соответствии с принятой нами системой определений иритерий качества классификации и алгоритм автоматической классификации вместе составляют процедуру решения задачи автоматической классификации. В следующем параграфе будет описан универсальный алгоритм автоматической классификации, основанный на критерии общего вида. В последующих двух параграфах мы подробно расьсмотрим два основных типа критериев качества классификации.
В последнем параграфе будет дана краткая характеристика некоторых других критериев и подведены итоги этой главы. 5 11.1. Алгоритм автоматической классификации 11.1.1. Распределение объектов по М классам. Алгоритм автоматической классификации, рассматриваемый в этом параграфе, пригоден для экстремизации широкого диапазона критериев.
Однако для описания алгоритма необходимо уточнить вид критерия, так же как и некоторые другие детали постановки задачи. Предположим, что мы хотим классифицировать У объектов, т;аждый из которых характеризуется и-мерным вектором, т. е. дано множество векторов (Хь Х2, ..., Х»~~. Мы не называем эти ,.векторы случайными, поскольку в задаче автоматической классификации они предполагаются фиксированными и известными. Каждый объект должен быть отнесен к одному из М классов, о»», ..., а,ь„где число классов М может быть, а может и небыть заранее известным. Класс, к которому относится 1-й объект, обозначим а»,„1= 1, ..., »1'. Для удобства будем предполагать, .что й» вЂ” целое число, закл|оченное между 1 и М.
Классификацией».' называют вектор, составленный из со», а конфигурацией 332 (11.1), ЛУ(г, Е, У) = пз1п ЛУ(г, у, 1). ~'(11.8) Х2 ° ° ХЖ] 'Х( ыот ) Х( 1 )г 1г (11.4)1 либо У (й,; Х*) = шах У (й; Х*). и (11.5)1 ГЛ, 11, АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ Хг' — вектор, составленный из Хн т. е. Й = [ог 1„огг„... ог„,,1' (11.2) Критерий качества классификации У является функ и " Й и Х*: *цией от У = У ~ог„„ог„„..., огА,„; Х„Х.„..., Хгг) = У (Й; Х~). (11.3): По определению, наилучшая классификация йо удовлетворяет УСЛОВИЮ 11.4 т В этом параграфе мы будем рассматривать лишь ус. е услови ( .
), так как для условия (11.5) рассуждение проводится а пал огич но. В задаче автомаг11ческой классификации конфигурация Х"' фиксирована. Алгоритм автоматической классификации модифп— цирует только классификацию й. Обычные методы поиска. экстремума здесь неприменимы вследствие дискретного и неупорядоченного характера множества возможных классификаций Тем не менее оказывается возможным построить итеративный поисковый алгоритм, использующий приращения критерия при.
вариациях й. Пусть на Е-й итерации мы имеем классификацию Й(У), где а (1) =- ~ы„, (1) ы„, (1)...., (1)1 . (11.6). Если изменить классификацию г-го объекта, перенеся его из клас— са Й;(1) в класс Х, критерий классификации изменится на величину ЛУ(1, у, 1), которая определяется выражением ЛХ (г, Х, ц = Х(ог„, (1),...,ог„, 1(1), огг, „, (1), ...,ог„,, (1); Х*). (11.7) Если величина ЛУ(Е, у, Е) отрицательна, то перенесение 1-го объекта в у-й класс дает улучшение классификации. На этом основан следующий алгоригм'. Шае 1.
Выбрать начальную классификацию гг(0). Шае 3. Для да~иной 1-й классификации 2(1) вычислить, Ы(г., У, 1) д У = 1, 2, ..., М и . = 1, 2, ..., Х з 11.1. АЛ1'ОРИТМ АВТОМАТИЧЕСКОИ КЛАССИФИКАЦИИ Шаг 8. Для всех 1=1, 2, ..., Л' перенести 1-и объект в класс Й, где 8 определяется из условия Если минимум ЛУ достигается прп нескольких значениях Х и если среди этих значений есть Й;(1), то неоднозначность разрешается в пользу уже построенной классификации, т. е.
берется у=В,(1). В противном случае неоднозначность разрешается произвольно. В результате получаем новую классификацию й(1+1). Шаг 4. Если О(1+ 1) Ф И(~), возвратиться к шагу 2; в противном случае работа алгоритма закончена. Этот алгоритм представляет собой итеративное применение решающего правила, основанного на критерии классификации.
Важно отметить, что на каждой итерации происходит одновременная перекласспфикация всех объектов. Таким образом, нег гарантии реального улучшения У и нет гарантии, что алгоритм сходится к абсолютному минимуму У. Поэтому по-настоящему оправдать использование этого алгоритма можно лишь результатами его экспериментальной проверки. Несмотря на эти потенциальные недостатки, описанный выше алгоритм, очень.
эффективен. Как и любой хороший поисковый алгоритм, он обеспечивает систематическое, направленное рассмотрение возмо;кных вариантов и позволяет ограничиться рассмотрением лишь небольшого подмножества класспфш'аций. Алгоритм легко программируется при любом критерии вида (11.3)"'). 11.1.2. Определение числа классов.
До спх пор мы игнорировали проблему определения числа классов ЛХ. Хотелось бы, чтобы процедура автоматической классификации позволяла не только найти классификацию, но и определить ЛХ. и Пусть Иж — множество всех классификаций Ж объектов на ЛХ классов. Наш алгоритм автоматической классифпкаци~и осум ществляет поиск только среди классификаций Йд.
Для большинства критериев 1 алгоритм генерирует ЛХ непустых классов, независимо от выбора ЛХ. Поэтому представляется необходимым иметь какой-либо метод выбора числа классов. К сожалени1о, одпной общепринятой теории для определения М не существует. Поэтому нам остается довольство~ваться описанием предложенных в разное время эвр|истических методов решения этой задачи.. ~) Необходимо отметить, что результаты работы этого алгоритма (н отечественной литературе его часто называют алгоритмом локальной оптимизации) существенно зависят от начальной классификации.
(Прим. род.) 334 ГЛ. 1К АВТОМАТИЧЕСКАЯ КЛАССИФИКАЦИЯ Объединение и расщепление. О сновнои алгоритм можно оо„ощить, введя в него процед ру об разования и разрушения классов в ходе итерационного процесса. Можно или объединить два класса в один класс, или расщепить класс на два разных класса. Объединение и расщепление классов используется в хорошо известном алгоритме автоматической классификации, получившем наименование 1ЯОРАТА 1Болл, 1965а, б~. На каждой итерации этого алгоритма вначале происходит перебрасывание объектов из класса в класс без изменения числа классов. Затем к имеющимся на данный момент П классам применяется процедура объединения или расщеплен л ния.
роцедура объединения объединяет в один класс каждую пару классов, средние векторы которых находятся друг от друга на расстоянии, меньшем заданного порога. Процедура расщепления расщепляет или не расщепляет каждый класс в зависимости от плотности его заполнения и свойств выборочной матрицы ковариацыи. П роцедуры объединения и расщепления чередуются от итерации к итерации. Само собой разумеется, что этот алгоритм является эвристическим. Его достоинство заключается в его эффективности и в том, что вмешательство человека в его работу сводится к минимуму. .Многократная дихотомия. В некотором отношении более предпочтительными являются методы, зависящие целиком лишь от критерия классификации 1. Один такой метод предложен в 1Ватанабе, 1969] и состоит в следующем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
