И.Д. Мандель - Кластерный анализ (1185344), страница 34
Текст из файла (страница 34)
Дать строгие правила применения того или иного способа классификации из такого их множества не представляется возможным. Например, рис. 4.4 описывает схему выбора всего лишь 13 расчетных величин, а здесь надо описать сотни. Есть и другое затруднение: далеко не про всякий алгоритм можно ясно сказать, в каких случаях он хорош, а в каких— плох (см. 2.4). Однако некоторые рекомендации сделать можно.
В табл. 4.1 сведены алгоритмы в соответствии с теми параметрами, которые исследователь в состоянии задать в процессе работы. Такая классификация может быть названа потребительской, ибо в конечном счете именно знание некоторых параметров идентифицирует любую содержательную постановку. В табл. 4.1 алгоритмы распределены по числу классифицируемых объектов. Оценки «до 200» и «более 200» являются прикидочными и основаны лишь на примерной информированности автора о временной и пространственной трудоемкости рассматриваемых алгоритмов. Решение этого вопроса, как уже отмечалось в 2.3.3, было бы чрезвычайно важным. Так что вполне возможны отдельные переносы алгоритмов из столбца в столбец, хотя для большинства процедур оценки близки к действительности.
Причем переносы возмо)кны только слева направо — все выделенные как быстрые алгоритмы действительно являются таковыми. При первом взгляде на таблицу бросается в глаза резкая асимметричность в распределении алгоритмов по видам используемых параметров. На рис.
4.5 изображены общие частоты встречаемости пороговых значений в алгоритмах разных типов в порядке убывания частоты; закон распределения носит явно гиперболический характер. Верхний график подтверждает это: левая часть гистограммы хорошо аппроксимируется логарифмически-линейной функцией, что свидетельствует о законе Ципфа в его ранговой форме [100[. Если следовать [100, 107 и др.], то наличие закона 148 о о о х к о о х о о. д о Ь и В 3 о. Ы о о о Й о о У о о о о.
о Я й а а о. Ю о ох х о х о Я а ю о о о. х ~о о" о й Ф х 3 й х Ф Ю Ю 'о щ 'о о сч,о о х' Я~ сч д" иЪ С'Ъ Сч сос4 Р ( ~ 40 со ио ~о ! со О .но ~ ь." ~." о с 5 ! ~о ж с4 х -я ~ох ~о .х сь"о~о~"х СЧ С4СЭ !о Ю о о х % о х о о о й о д ооо оо аоо хо„ х ххх „хо х дх хо е о. й ойдо х х о хода х х оооо х х а о о ох о о,о оооо хдоо ~- о ~ о. ' о. х и й Д х ( % й о х о о.
о о 1о о о о Й х о о о о 3 о о, О 1 149 о о х х о о о о М о. о о. Ю Ф о а Ь о. о 'о Ф о д и„ о Х 5 .б о о а Ф й о о д Ф о Х о д о ~~ ох ха 5 о. ц~ о о о о о о. ( о О о о о о. Ь. Ф д Ф Т о о о ( о оо о о 1 о оо х ю ,о — а к о о ь о й о М о. х а Ф о о о оо о /д~ о дй о ~- $ о и о о И о $ Д б -о ф с~ '~ Ю о.,„ М О оФ о Ф й о о о о о а а о. ( о 4 я о Дй Ы й о Ципфа говорит о достаточной структурированности научной дисциплины. Следовательно, и в будущем можно ожидать появления все большего числа работ в условиях отсутствия параметров, при заданном числе классов или при заданном пороге типа расстояния до центра класса.
Видимо, эти три режима воспрннимаготся 10010' 1,В 1,4 1,2 о.в 0,4 0.2 55 45 35 25 15 к Ф в о„, а й о ар е Ф а Ь г Рнс. 4.5. Частоты встречаемостн задаваемых параметров в нластериом анализе (!) и их логарифмы; И вЂ” отсутствие параметров, !!, а, Ь вЂ” параметры алг. 49, 66, 56; ! — алг. 43 !5! специалистами как самые благоприятные. Между тем число объектов в классе, внутриклассовая дисперсия показателей и др. используют. ся значительно реже. Способы обоснования значений параметров рассмотрены в 4.2.3.
Табл. 4.1 может служить основанием для выбора подходящих алгоритмов классификации. Видно, что если исследователь в состоянии как-то зафиксировать свои представления о задаваемых параметрах, то число возможных алгоритмов становится не таким уж большим (в самой заполненной клетке таблицы — 21 алгоритм). Кроме этого, множество прямых процедур можно стратифицировать еще в двух разрезах табл.
2.1: по такому важному свойству, как зависимость результата работы от порядка просмотра точек (видимо, .при прочих равных условиях лучше выбирать алгоритмы, инвариантные к номерам объектов), и по наличию или отсутствию пересекающихся кластеров. Сочетание таблиц 2.1 и 4.1 позволяет еще более сократить множество алгоритмов, удобных для решения конкретных задач. Наконец, некоторая информация содержится в 2.4, где рекомендованы наиболее устойчивые процедуры из числа !4 рассматриваемых. При наличии приводимых в 2.4 оговорок для всех (проверяемых там) ситуаций лучшими оказались алгоритмы Уорда (8), Болла и Холла с эвристикой Боннерв (39+33=39') и с максимально удаленными эталонами (39+45=39") и дальнего соседа (3).
Алгоритм Наги и Шелтона (60) носит весьма специфический характер и не может быть непосредственно рекомендован, как и алгоритм Розенблатта (58). Алгоритмы 33 и 46, как носящие вспомогательный характер и включенные в алгоритм 39, из рассмотрения убираются. Метод «вроцлавской таксономии», идентичный алгоритму ближнего соседа (54), будет давать, видимо, в целом ненадежные результаты, как и сам односвязывающий метод (см. 2.4). Это не надо, конечно, понимать как «исключение из оборота» перечисленных алгоритмов, особенно метода ближнего соседа.
Большая подборка материалов (127] посвящена сравнению лишь двух процедур — дальней и ближней связи, и там есть много интересных сведений о разных аспектах работы этих алгоритмов. Речь идет лишь о том, что на первичном этапе, без априорных предположений о характере структуры совокупности, лучше пользоваться менее чувствительными алгоритмами, чем ближний сосед и его модификации (см. 2.4). С учетом этих обстоятельств можно построить дополнительную схему выбора прямых алгоритмов для самых заполненных клеток табл. 4.1.
Она отражена в табл. 4.2. Как видно из таблицы, в каждой группе совсем немного алгоритмов, из которых сравнительно нетрудно сделать выбор, учитывая естественную ограниченность программного обеспечения. Относительно человеко-машинных методов классификации в табл. 4.1 можно повторить сказанное в 2.2: во всех поисковых задачах не слишком большой размерности их использование очень желатель- 152 Т а б л и и а 4«Д Рекомендуемые алгоритмы прямой автоматической классифнканни для применения в обычных условиях' ' Пересекающиеся кластеры — в методах бу, 61, 65.
Некоторые из «отброшенных» методов могут применяться, когда есть гипотеза о невыпуклости и пр., — см, ниже. но — один вид упорядоченной матрицы (например, близкой к выпуклой) способен сказать исследователю очень много о структуре данных. Не случайно этот прием успешно применяют и в образном анализе 1128]. Рассмотрим алгоритмы оптимизации. Видно, что почти все они сконцентрированы в верхней части табл. 4.1; попробуем «разукрупнить» три самые плотные клетки. Самый надежный способ обоснования вида критерия — это придание ему четкого содержательного смысла, совпадающего с конечным результатом, найденным в данной задаче или максимально близким к нему.
Пример четкой экономической трактовки дает функционал гя, если требуется выделить блоки отраслей по их межотраслевым связям так, чтобы суммарный обмен товарами в блоке был максимален, а между блоками — минимален, естественнее всего испольэовать Ри; этот же критерий пригоден для оптимальной группировки энергохозяйств в управляемые объединения, при которой желательна минимальная внешняя связанность каждой системы; при географическом районировании могут иметь особое значение критерии типа г«, Рзз, Рзз, Рзз, г«е, г4ь поскольку там существенны расстояния до центров агломераций, под которыми понимаются не столько «центры тяжести» населенных пунктов, сколько отдельные города или транспортные узлы и т.
д. Эти же критерии логично использовать во многих других ситуациях, где предполагается некая «экстремальная точка» в каждом классе (см. Рзь гзз): узловое событие исторического периода (и события, тяготеющие к нему); лидирующая страна и сателлиты; ведущий ученый школы и окружающие его лица; психологический лидер группы и т. д. В двух последних примерах уместно использовать вариант г«о с несколькими эталонами, так как лидеров в группе может быть 2 — 3. В более размытых ситуациях такого же типа (с эталонами) целесообРазно пРименЯть Размытые кРитеРии Рзв и особенно гт«з.. например, в группировке людей по уровню интеллекта лидеры в классах наверняка будут, но недостаточно четкие (каждый будет в определенной мере представлять «прототип» группы). Критерии типа «средние расстояния вне и внутри» Ре — Рв, Рзе, Рзо воз- Гбз никают в классификации нецентрированных систем, например, при распределении элементов на отдельных блоках платы требуется максимизировать интенсивность взаимодействия между элемен.
тами одного блока и минимизировать взаимодействие между блоками. Словом, самый лучший способ выбрать критерий — это сформулировать его на языке, близком к экономическому: какие потери будут иметь место при отклонении от экстремального значения показателя. Это вдвойне справедливо для критериев, у которых можно отыскать глобальный экстремум (Еь Ень Ем, Ежь Еы), При отсутствии точной постановки точное решение не стоит затрат на его получение. А как быть в типичной ситуации поискового статистического исследования, когда исследователь мало представляет себе структуру данных и еще меньше — содержательный смысл тонкой разницы между различными критериями? Функционалы обладают определенными формальными свойствами, которые можно учитывать при решении конкретных задач.
Отметим сразу, что фактически все алгоритмы, минимизирующие критерии, зависят от порядка просмотра точек. Критерии качества можно разбить на два неравных класса по следующему принципу: использует функционал метрические свойства расстояния (осредняет их, возводит в степень и т. д.) или только качественные (порядковые или номинальные). Критерии второго типа в целом более предпочтительны в тех случаях, когда нет уверенности в «истинности» вычисленных мер близости. К таким непараметрическим критериям относятся Ем Ень Емь Егь, Е»ь Емь Емь Ем. Вопрос о соответствии между видом используемого критерия и геометрической формой выделяемых' кластеров исследован недостаточно.
Ясно лишь, что все перечисленные в 2.3.2 критерии «с центром», а также дисперсионные критерии Еь Ен — Ем ориентированы на выделение шарообразных (в своей метрике) скоплений. Хотя в реальности такие кластеры довольно нередки, ими, конечно, не исчерпывается многообразие возможных форм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
