Техническая документация

Назначение таксономии. Первичные данные о качестве продукции, сведенные в таблицу типа объект-свойство (ТОС), часто бывают необозримыми для непосредственного восприятия отношений между объектами. Понимание материала облегчается, если его удается описать более кратким способом.
Традиционный способ сокращения описания связан с разделением множества М объектов таблицы на небольшое число групп объектов, связанных друг с другом каким-нибудь закономерным свойством. Обычно в качестве такой закономерности используется «похожесть» объектов одной группы или друг на друга или на некоторый один «типичный» объект.
Всякие закономерности ищутся для практического удобства. Закономерности «групповой похожести» позволяют сильно сократить описание ТОС при малой потере информации. Вместо перечисления всех объектов можно дать список типичных (эталонных) представителей групп, указав номера (имена) объектов, входящих в состав каждой группы, и средние или максимальные отличия их свойств от эталонов. При небольшом числе групп описание данных становится обозримым и интерпретируемым.
Такая группировка делается с помощью методов таксономии. Синонимами термина «таксономия» служат термины «кластерный анализ», «автоматическая классификация», «самообучение».
Алгоритмы таксономии отличаются друг от друга процедурами группировок и критериями качества классификации.
Пусть данные некоторой таблицы Т, подлежащие таксономии, содержат т объектов (аь ..., ат), описанных п свойствами. Требуется выявить к таксонов, к — 1, т. Варианты разбиения объектов на к таксонов будем сравнивать по критерию качества Р.
Свойства можно представить в виде координат метрического пространства, тогда каждый объект со своими свойствами будет отображаться в некоторую точку этого пространства. Два объекта с почти одинаковыми свойствами отобразятся в две близкие точки, а объекты с сильно отличающимися свойствами будут представлены далекими друг от друга точками. Если имеются сгустки точек, отделенных промежутками от других сгустков, то их целесообразно выделить в отдельные структурные части множества — в классы (кластеры, таксоны). Признаки X, характеризующие свойства объектов и влияющие на их качество, при удачной таксономии в один таксон будут попадать объекты, мало отличающиеся друг от друга по качеству. Таким путем можно получить описание к таксонов, каждый из которых (}-й таксон) объединяет объекты с качеством. В дальнейшем любой новый объект, описанный набором характеристик х1г ..., хп, с помощью процедур распознавания образов может быть автоматически отнесен к тому или иному классу (таксону) по качеству.
Алгоритмы семейства РОКЕЬ. Отличительная черта этого семейства алгоритмов состоит в том, что все они выделяют таксоны простой сферической формы. Разные алгоритмы этого семейства отличаются друг от друга тем, задается ли число таксонов к пользователем или выбирается автоматически, с большими ли массивами данных они могут работать или только с такими, которые умещаются в оперативную память; поступают ли объекты параллельно или последовательно. Начнем с описания основного (базового) алгоритма таксономии из этого семейства.
Алгоритм таксономии работает с объектами, описанными количественными характеристиками. Объекты, включенные в один таксон, попадают в гиперсферу с центром с и радиусом Изменяя радиус, можно получать различное число таксонов к. При фиксированном радиусе Я алгоритм РОНЕЫ работает следующим образом. Центр гиперсферы радиуса В. помещается в любую точку множества объектов. Определяются точки, которые оказались внутри этой сферы. Для этого вычисляется расстояние р от точки с{1) до всех М точек, и те из них, для которых р ^ /?, считаются внутренними.
Вычисляется центр тяжести внутренних точек, и центр сферы перемещается в этот центр тяжести с(2). Для нового положения сферы находятся снова внутренние точки и их центр тяжести. Процедура повторяется до тех пор, пока не перестанут изменяться координаты центра тяжести. При этом гиперсфера останавливается в области локального экстремума плотности точек исходного множества А. Назовем эту сферу с ее внутренними точками таксоном Эти точки из дальнейшего рассмотрения исключаются. Затем центр следующей такой же гиперсферы совмещается с любой из оставшихся точек, и процедура выделения таксонов повторяется до тех пор, пока все исходное множество объектов не будет разделено между таксонами.
Очевидно, что количество таксонов к тем больше, чем меньше радиус таксона Я- Желательное для пользователя количество таксонов может быть найдено соответствующим подбором радиуса Я • С этой целью радиус последовательно изменяется с равномерным шагом Д/? от Ятах, при котором все исходные точки объединяются в один таксон до тех пор, пока не будет получено количество таксонов, ближайшее к заданному к.
В процессе такой работы алгоритм РОКЕ1Л выдает серию таксономий, каждая последующая таксономия отличается от предыдущей уменьшением размера таксона (радиуса Я) и увеличением их числа. Такая последовательность дробной классификации позволяет проследить «генезис» таксонов, увидеть, на какие мелкие таксоны распадается тот или иной крупный таксон. При одном и том же числе таксонов к разные варианты таксономии отличаются по качеству.
Алгоритм РОКЕЫ дает решение за конечное число шагов, однако очевидно, что решение бывает не единственным. Выбор одного решения из некоторого их числа делается по критерию качества Р, который для алгоритма РОКЕ1Л выглядит следующим образом.
Лучшему варианту таксономии будет соответствовать минимальное значение критерия Р. Выбор такого критерия обосновывается распространенными интуитивными правилами «ручной» группировки. Обычно специалисты объединяют в одну группу объекты, по возможности мало отличающиеся друг от друга или от типичного (базового) объекта, ближайшего к центру таксона. В дальнейшем будут рассмотрены и другие критерии качества.
Алгоритм РОКЕ1Л заканчивает работу, когда впервые получается число таксонов к' к. Если пользователю необходим один вариант таксономии, разделенный точно на к таксонов, то ему следует пользоваться алгоритмом.
Алгоритм РО К Е Ь 2 предназначен для получения заданного числа сферических таксонов. В отличие от РОКЕЫ радиус Я в этом случае изменяется не с постоянным, а с переменным шагом, .который на каждом очередном шаге (варианте таксономии) уменьшается вдвое, так что при поиске 1-го варианта таксономии радиус сферы равен.
Алгоритм $КАТ. На практике возможны случаи, когда нет уверенности в устойчивости полученных решений.
Проверку таксонов на устойчивость можно выполнить строгими статистическими методами. Однако эти методы разработаны пока что для одномерных нормальных распределений. В многомерном распределении используются нестрогие эвристические приемы. Один из таких приемов реализован в алгоритме 5 КАТ.
Сначала осуществляется таксономия объектов при фиксированном радиусе с помощью алгоритма РОКЕЫ. Затем каждый таксон испытывается на устойчивость. Для этого восстанавливаются
все точки, и сферы радиуса Я запускаются поочередно из центров всех полученных таксонов. Одни сферы остаются на месте, другие скатываются к центрам таксонов-предшественников. Решение алгоритм 5 КАТ выдает в виде перечня всех устойчивых таксонов и указания, какие из неустойчивых таксонов к ним тяготеют.
Иногда пользователю достаточно знать только устойчивые таксоны. Остальные объекты он считает нехарактерными, т. е. представителями «серого фона». Такое решение эквивалентно тому, что максимизируется функционал.
В других случаях пользователь склонен видеть в материале, состоящем из к' устойчивых и к — к' неустойчивых таксонов, наличие таксонов сложной формы, образованной объединением нескольких пересекающихся сфер. Однако при одинаковом числе к таксонов таксономия кажется тем лучше, чем большее число объектов находится в устойчивых таксонах, так что и в этом случае фактически используется последний из приведенных критериев качества таксономии.
Алгоритм КОЬАР5. Задачу поиска таксонов на «сером фоне» с автоматическим выбором числа таксонов и их радиусов решает алгоритм КОЬАРВ. Его можно разделить на два этапа. На первом этапе ищутся точки, которые с большой вероятностью могут оказаться центрами будущих таксонов. На втором этапе делается проверка, действительно ли выбранные точки являются центрами таксонов.
Процедуры первого этапа выполняют следующие функции. Вначале сфера достаточно большого диаметра (радиуса Яо) помещается в любую точку множества и смещается, как в алгоритме РОКЕЬ, в центр локального
сгустка. Затем радиус уменьшается на величину Д/?0. При этом центр тяжести «внутренних» точек может сместиться, и сфера сдвинется в район еще более плотного сгустка. Как только эта сфера остановится, радиус снова уменьшается на Л#0- Такая процедура повторяется вплоть до достижения заданного значения.
Число внутренних точек этой сферы используется в качестве характеристики локальной плотности распределения. Если эта плотность выше некоторого порога, то центр сферы выбирается в качестве потенциального центра таксона, а точки, попавшие в него, из дальнейших шагов первого этапа исключают. Затем центр новой сферы того же большого радиуса Д?0 помещается в любую из оставшихся точек, и процесс движения сжимающейся сферы повторяется. Добавляются новые сферы радиуса некоторое число Н раз. В итоге запоминаются п точек, плотность в районе которых превышает некоторый заданный порог. Точки упорядочиваются по мере убывания плотности, и на этом первый этап заканчивается.
Второй этап состоит в том, что центры сфер радиуса               помещаются в выбранные точки (поочередно, начиная с первой в упорядоченном списке) и сферы начинают расширяться на величину радиуса Д/?, при каждом новом радиусе сфера может сместиться в центр тяжести множества внутренних точек. Сфера перестает увеличиваться на 1-м шаге, если число внутренних точек на (* — 1)-м шаге отличается от числа внутренних точек на *-м шаге на величину, меньшую ДI (%). Это значит, что на 1-м шаге сфера вышла в разреженное пространство за границы плотного таксона.
При заданных параметрах /?0, Д/?0, &ш1п» Л, А/? алгоритм максимизирует функционал качества таксономии такого вида: где к — число полученных таксонов.
Точки редкого фона, не включенные в получившиеся таксоны, могут по желанию пользователя присоединиться.
Алгоритм РОЯБЬ 5. Для ряда классификационных задач исследования качества технических устройств и технологических процессов используются таблицы данных, содержащие только бинарные признаки. Для таксономии таких данных можно применять алгоритм. Отличие его от алгоритма РОКЕ1Л состоит только в способе вычисления расстояния между объектами (классами, таксонами), а также в том, что центры сфер перемещаются не в непрерывном пространстве, а в дискретном и находятся всегда в одной из вершин единичного УУ-мерного куба.
Параметрами, от которых зависит результат таксономии, служат желаемое число таксонов к и шаг уменьшения радиуса таксона ДЯ (обычно 0.1 Я тах» где ^тах — расстояние от центра тяжести всех объектов до самой удаленной точки). При этом алгоритм РОКЕЬ5 минимизирует сумму расстояний от всех точек а& до центров своих таксонов.
Алгоритм В1СРОК. В классификационных задачах качества объектов могут иметь место достаточно большие массивы данных, которые не умещаются в оперативную память и хранятся на внешнем машинном носителе (например, ленте или диске). Таксономия таких массивов может быть осуществлена с помощью итеративного алгоритма данных ВЮРОК.
Вначале в оперативную память из общего числа т объектов вводится максимально возможное их число V. Алгоритмом РОК,ЕЬ2 разделяются V точек на к' таксонов, к' к. Описание таксона состоит из координат типичной точки, ее номера и количества входящих в таксон объектов.
После того, как будет получено к[ таксонов на первой порции данных из V объектов, описание этих таксонов переносится на отведенное в памяти место или на внешний носитель, а в оперативную память заносится следующая часть таблицы (новых V объектов). После повторения этой процедуры / =  раз, т. е. когда будут обработаны все т объектов, образуется массив описания <7 = таксонов (при размещении описания таксонов в оперативной памяти предусмотрен контроль заполнения отведенного в памяти места). Это описание затем рассматривается в качестве нового массива данных, а типичные точки каждого выделенного таксона — в качестве отдельного объекта, подлежащего таксономии. Дальнейшая группировка этих <7 промежуточных таксонов в к более крупных таксонов может выполняться любым из описанных выше алгоритмов таксономии.
Предусмотрена возможность задания ограничения на минимальное количество ф точек в таксоне, т. е. выделяются к таксонов только с количеством точек в каждом из них.
После того, как закончен цикл обработки т объектов, найдены требуемые к центров, производится перераспределение каждого из т объектов по к таксонам. Объект приписывается к тому таксону, расстояние до центра которого оказалось минимальным.
Для того чтобы до некоторой степени устранить возможный дефект таксономии по частям, после окончания цикла обработки осуществляется переформирование массива исходных данных таким образом, чтобы на следующем цикле в каждую порцию из V объектов попадали точки наиболее близких таксонов. На переформированном массиве т объектов повторяется полный цикл разбиения на к таксонов. В программах количество таких циклов определяется заданием параметра.
Если объем данных достаточно велик, что <7 > V, то процедура укрупнения таксонов будет не двух, а многоступенчатая. Скатывание таксонов во все более крупные сферы потребуется делать несколько раз. При этом крупные таксоны будут иметь иерархическую структуру: на каждом следующем уровне иерархии располагаются все более мелкие таксоны, а на последующем уровне — отдельные объекты. Информация об этих структурных отношениях между объектами и их группами иногда бывает полезной для более глубокого понимания природы изучаемых объектов.
Представим эту структуру в виде де-рева-графа, общая вершина которого помещается в центр тяжести всех объектов. Первые ветви соединяют эту вершину с центрами к самых крупных таксонов, ветви следующего уровня соединяют эти центры с центрами мелких таксонов, входящих в их состав, и так далее вплоть до последнего уровня, где ветви соединяют центры самых мелких таксонов с отдельными объектами.
Алгоритм В ЮРОК гарантирует минимум суммарной длины Р всех этих ветвей: где й-1 — длина 1-й ветви; р — общее число ветвей в графе.
Алгоритмы семейства ККАВ. В основе алгоритмов данного семейства таксономии положены меры, использующие свойства кратчайшего незамкнутого пути (КНП). КНП — это граф, который соединяет все точки множества и при этом не имеет петель (циклов), а сумма длин всех его ребер минимальна.
Если разрезать (к — 1) ребро КНП, то будет выделено к таксонов. Мерой близости объектов внутри таксонов можно считать среднюю длину ребер КНП, соединяющего все точки данного таксона.
Проверка на двумерных примерах показала, что чем лучше таксономия, тем больше Р. При изменении параметра к функция Р проходит через локальные экстремумы в тех точках, когда количество таксонов совпадает с тем количеством, которое обычно указывает и человек при ручной таксономии того же множества объектов. Выделяемые при этом таксоны могут иметь любую форму.
Алгоритм ККАВ1 работает следующим образом. Вначале проводится кратчайший незамкнутый путь между всеми точками множества. Если задано число таксонов А, то путем перебора находятся такие (к — 1) ребра, проведение границ по которым дает максимальное значение функционала качества Р.
Если число объектов и количество таксонов велики, перебор становится практически неприемлемым. Для его сокращения используется предварительный отбор ребер-претедентов, т. е. ребер, по которым с большой вероятностью могут пройти границы. Это делается путем оценки для всех ребер КНП и отбором тех из них, для которых < А-о (например, < 1). Из рассмотрения исключаются ребра, которые короче самого короткого из примыкающих к нему ребер.
В некоторых случаях на практике не важна равномерность таксонов по числу объектов. В этом случае используется модификация критерия качества.
Алгоритм К К А В 2 используется при большом числе объектов пг исходного множества, когда затруднителен этап построения КНП. Для ускорения процедуры таксономии на •первом этапе алгоритма ККАВ2 используется программа РОКЕ1Л, которая делает группировку т объектов в к' таксонов (к < к' < пг). Затем центры этих мелких таксонов служат объектами таксономии по алгоритму ККАВ1. Небольшое отличие на этом этапе состоит в том, что при вычислении параметра к можно учитывать центры таксонов с равными их весами, а можно и с весами, пропорциональными числу включенных в них исходных объектов. Можно, как и в предыдущем случае, не использовать параметр к, если предположить, что интерес могут представлять как таксоны-гиганты, так и таксоны-карлики.
Алгоритмом ККАВ2 обычно пользуются при т > 50.
Алгоритм ^ОINТ. Алгоритмы ВЮРОК и ККАВ2 используют процедуру укрупнения мелких таксонов сферической формы, полученных алгоритмом РОКЕ1Л. Может возникнуть необходимость объединения к таксонов произвольной формы произвольного происхождения в более крупных таксонов. Для этих целей и используется алгоритм .ЮШТ. Этот алгоритм работает таким образом. Строится КНП внутри каждого мелкого таксона, а затем КНП между ними — путем соединения ребрами ближайших точек разных таксонов. Вычисляется критерий Р качества этой исходной информации. Затем поочередно объединяются все пары смежных таксонов (соседних по КНП). При каждом объединении вычисляется величина критерия Р*. Выбирается вариант объединения, дающий. Такая процедура объединения смежных пар повторяется до получения требуемого числа таксонов кг.
Наблюдая за изменением Р на каждом шаге, можно найти наиболее предпочтительное число таксонов в диапазоне от к до кг. На каждом шаге алгоритм гарантирует наилучший вариант уменьшения числа таксонов на единицу, что, однако, не гарантирует получения глобального оптимального варианта объединения к мелких таксонов в кг крупных. Кроме того, сами исходные таксоны могут не соответствовать наилучшей с точки зрения алгоритма ККАВ таксономии. Таким образом, результаты таксономии исходного множества т объектов и к промежуточных таксонов на кх таксонов могут быть разными. Алгоритм ,ЮШТ максимизирует величину к—кх1 = 1, где Р1 — значение критерия качества на 1-м шаге укрупнения таксонов.