18. Классификация методов таксономии

По типу разделения

Иерархические

Иерархическая таксономия

Разделительные

k-Means

Forel

Логические алгоритмы таксономии

По базовой гипотезе

Вероятностные

ищутся параметры смеси распределений

EM-алгоритм

Геометрические

ищутся связные группы объектов

KRAB

По суперцели

Алгоритмы Forel и Scat Алгоритм FOREL.

Таксоны, получаемые этим алгоритмом, имеют сферическую форму. Количество таксонов зависит от радиуса сфер: чем меньше радиус, тем больше получается таксонов. Вначале признаки объектов нормируются так, чтобы значения всех признаков находились в диапазоне от нуля до единицы. Затем строится гиперсфера минимального радиуса , которая охватывает все  точек. Если бы нам был нужен один таксон, то он был бы представлен именно этой начальной сферой. Но такое огрубление экспериментального материала нас обычно не устраивает, и мы пытаемся получить большее количество таксонов.

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

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

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

Алгоритм SCAT.

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

Каждый очередной таксон находился нами в условиях, когда точки, попавшие в предыдущие таксоны, исключались из рассмотрения. А что происходит, если таксоны формируются в присутствии всех  точек? Может случиться, что некоторые из более поздних таксонов включат в свой состав точки, ранее вошедшие в другие таксоны, и не останутся на месте, а станут скатываться в сторону соседнего сгустка точек и сольются с одним из своих предшественников. Такая ситуация изображена на рис. 6: таксон 2 начнет смещаться и сольется с таксоном 1. Другие же таксоны останутся на прежнем месте и с прежним составом своих внутренних точек. Будем считать таксоны 1, 3 и 4 устойчивыми, самостоятельными, а таксон 2 — неустойчивым, случайным. Случайные таксоны могут появляться из-за помех в данных или из-за неудачного выбора радиуса сфер.

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

Один из таких приемов реализован в алгоритме SKAT. На вход программы подается множество  объектов и результаты его таксономии  с помощью алгоритма FOREL при радиусе сферы, равном . Процедуры таксономии повторяются с таким же радиусом сфер, но теперь в качестве начальных точек выбираются центры, полученные в таксономии , и формирование каждого нового таксона делается с участием всех  точек. В результате обнаруживаются неустойчивые таксоны, которые скатываются к таксонам-предшественникам. Решение выдается в виде перечня устойчивых таксонов и указания тех неустойчивых, которые к ним тяготеют. Если мы хотим ограничиться только устойчивыми таксонами, тогда мы должны стремиться к такому варианту таксономии, при котором количество точек в устойчивых таксонах было бы максимальным, т. е. максимизировать функционал

, где

Задачи таксономии природа задач таксономии.

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

Как же делается таксономия? Одно и тоже множество из то объектов можно разбить на  таксонов  по-разному. Если бы мы записали такое исходное состояние нашего знания в виде эмпирической гипотезы , то ее тестовый алгоритм  считал бы допустимой любую таксономию. Но мы знаем, что человек, делая группировку чего бы то ни было, руководствуется каким-то критерием (обозначим его ), который позволяет отличать хорошие группировки от плохих и выбирать наилучший вариант таксономии. Теперь наше знание позволяет сформулировать более сильную гипотезу, тестовый алгоритм которой считает допустимой только такую таксономию, которая удовлетворяет критерию .

 

Иерархическая таксономия.

Можно считать, что исходное множество  точек представляет собой результат таксономии с радиусом , при котором получается  таксонов, каждый из которых содержит по одной точке. Применим к ним алгоритм BIGFOR, исключив из него описанную выше процедуру перераспределения точек. На первом шаге алгоритма BIGFOR выбирается небольшой радиус , дающий  таксонов первого уровня. На втором шаге происходит слияние некоторых близких друг к другу мелких таксонов в более крупные, в результате чего появляются  таксонов второго уровня . Если эти шаги продолжать, то на некотором шаге  будет получена таксономия, объединяющая все точки в один-единственный таксон.

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

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

Динамичная таксономия

Иногда возникает ситуация, когда таксономию нужно делать не на одновременно заданном множестве объектов, а на объектах, возникающих по одному или небольшими группами в ходе исследуемого процесса. При этом таксономия может меняться после появлении каждого нового объекта и окончательный вид она приобретает тогда, когда обработан последний из исследуемых объектов. Таким образом, по ходу процесса происходит свертка информации: вместо характеристик отдельных объектов нужно хранить лишь краткое описание полученных к данному моменту времени таксонов с указанием числа объектов, включенных в каждый таксон.

Таксономия с суперцелью

Выбор числа таксонов

Иногда встречаются случаи, когда заказчик (владелец данных) точно знает, сколько таксонов он хотел бы получить.

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

Базовые гипотезы, лежащие в основе методов анализа данных

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

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

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

Дополнительные гипотезы могут носить общий характер или касаться мелких частностей. Здесь будут описаны две базовых гипотезы — компактности и -компактности [74] — и показано их влияние на характер алгоритмов анализа данных.

Гипотеза компактности

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

Конечно, она подтверждается не всегда. Если, например, среди признаков имеется много случайных, неинформативных, то точки одного образа могут оказаться далекими друг от друга и рассеянными среди точек других образов. Но дополнительно предполагается, что в многомерном признаковом пространстве уже было найдено такое (информативное) подпространство, в котором точки одного класса действительно образуют явно выделяемые компактные сгустки. Назовем  признаков, входящих в информативное подмножество , описывающими, а номинальный -й признак , указывающий имя образа, целевым. Обозначим множество объектов обучающей выборки через , новый распознаваемый объект через , а тот факт, что объекты множества  компактны (эквивалентны, похожи или близки друг другу) в пространстве  характеристик  — через . Мера компактности может быть любой: она может характеризоваться средним расстоянием от центра тяжести до всех точек образа; средней длиной ребра полного графа или ребра кратчайшего незамкнутого пути, соединяющего точки одного образа; максимальным расстоянием между двумя точками образа и т. д. Например, компактными (эквивалентными) считаем два объекта, если все признаки одного объекта равны соответствующим признакам другого. Или: объекты компактны, если евклидово расстояние между векторами их признаков не превышает величину .

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

Гипотеза λ-компактности

Гипотеза компактности оперирует абсолютными значениями расстояний между векторами в пространстве характеристик. Однако на некоторых примерах можно показать, что важную роль в задачах анализа данных играют не только сами расстояния, но и отношения между ними. Так, расстояние между точками 5 и 6 на рис. 2, а меньше, чем между 6 и 7, но, делая «вручную» таксономию этого множества точек на два таксона, эксперты обычно проводят границу по ребру 5-6. Глаз человека улавливает на этой границе нарушение однородности расстояний между соседними точками и придает этому факту большее значение, чем абсолютной величине расстояний.

Зрительный аппарат человека обладает уникальными способностями делать классификацию (таксономию) множества объектов, если они представлены точками на плоскости [68]. На рис. 3 представлены примеры множеств, таксономия которых для человека не составляет труда. Результаты получаемой при этом естественной для человека таксономии (два сгустка и фон) не могут быть получены или объяснены с позиций гипотезы компактности. Гипотеза же -компактности позволяет легко получать и просто объяснять такие результаты.

28.  Критерии информативности признаков

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

Если распределение реализаций каждого образа подчиняется нормальному закону с диагональными матрицами ковариаций (при этом поверхности равной плотности представляют собой сферы одинакового радиуса), то мерой трудности распознавания , обратно пропорциональной ожидаемым потерям, может служить среднее значение евклидова расстояния между математическими ожиданиями всех пар образов:

где  — евклидово расстояние между математическими ожиданиями -го и -гo образов.

29. алгоритм Del

Оценим ошибку распознавания при использовании всех 50 признаков . Затем исключим из системы первый признак и найдем ошибку , которую дают оставшиеся 49 признаков. Поменяем ролями первый и второй признаки и найдем ошибку  в новом 49-мерном пространстве. Эту операцию поочередного исключения одного признака проведем 50 раз. Среди полученных величин  найдем самую малую. Она укажет нам на признак, исключение которого из системы было наименее ощутимым. Исключим этот признак из системы и приступим к испытанию оставшихся 49 признаков. Их поочередное исключение из системы позволит найти самый неинформативный и снизить размерность пространства до 48. Эти процедуры повторяются  раз, т. е. до тех пор, пока в системе не останется заданное число признаков .

Количество проверяемых систем признаков при этом методе выражается следующим равенством:

что значительно меньше, чем . В нашем примере , что на 12 порядков меньше объема полного перебора.

 Метод последовательного добавления признаков (алгоритм Add)

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

Трудоемкость этого алгоритма приблизительно такая же, как и алгоритма Del, однако результаты, получаемые алгоритмом Add, обычно лучше, чем у Del. Объясняется этот факт влиянием малой представительности обучающей выборки: при одном и том же объеме выборки чем выше размерность признакового пространства, тем меньше обоснованность получаемых статистических выводов (в нашем случае — оценки информативности). Средняя размерность выборочного пространства в алгоритме Del равна , а в алгоритме Add — , так что риск ошибочного признания информативного признака неинформативным в Del выше, чем в Add.

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