И.Д. Мандель - Кластерный анализ (1185344), страница 17
Текст из файла (страница 17)
Алгоритмы типа диагонализации матрицы расстояний. Оговоримся сразу, что под термином «днагонализация» мы понимаем такую перестановку строк и столбцов матрицы расстояний, при которой по диагонали располагаются блоки малых расстояний. В широком смысле [16[ предполагается у полученной упорядоченной матрицы наличие некоторых экстремальных свойств. В поисковых задачах алгоритмы типа 21 — 29 для небольшого числа объектов (не более 50 — 70) представляются нам самыми удобными процедурами кластерного анализа. Если считать, что вся информация о структуре множества в многомерном пространстве содержится в матрице расстояний, то диагонализация перестраивает матрицу так, что суждение о структуре становится наиболее обоснованным.
Не случайно алгоритмы в своем большинстве реализуют принцип свободной классификации и являются человеко-машинными. При анализе упорядоченной матрицы человеку представляется возможность принимать любое решение, связанное с классификацией: варьировать границы классов, следить на качественном уровне за изменением состава классов, решать вопрос о пороговой величине. Можно 7З считать все расстояния в классе не превышающими некоторого числа либо включать в класс такой объект, что его расстояние до одного-двух объектов класса больше порога, но это не меняет сути кластера. Такие операции трудно формализовать, а для конкретного случая и невозможно. Наконец, если в дополнение к упорядоченной матрице ЭВМ выдает функцию степени близости объектов к классу типа описанной в алг. 28, это еще более облегчает принятие правильного решения.
Если в иерархических процедурах можно наблюдать лишь часть связей между объектами, то в упорядоченных матрицах — все связи. Это дает возможность быстрой проверки любой гипотезы о 'правомерности переноса объекта из класса в класс, объединения классов (следя за блоками межклассовых расстояний). Хорошо виден характер пересечения классов: общие объекты искажают блочную структуру матрицы. Решение об их классификации можно принять на качественном уровне либо воспользоваться дополнительными расчетами. Вопрос о зависимости результатов работы алгоритмов от порядка просмотра точек является не вполне ясным. Все алгоритмы начинают работу с произвольно взятого объекта, и дальше идет упорядочение остальных объектов. В принципе зависимость от выбора начального объекта есть, но, как показали наши эксперименты, очень слабая.
Можно всегда начинать процесс, например, с пары наиболее близких объектов. Во всяком случае утверждение в !15] о полной независимости алгоритма от начала работы не вполне верно. Но на конечный результат, действительно, первая точка практически не влияет: в силу удобства человеко-машинных операций, описанных выше, любые сдвиги в матрице легко поправляются. Алгоритмы трудоемки, как и иерархические процедуры, поэтому для больших матриц использоваться не могут. Более того, если на иерархическом дереве, например, из !50 объектов еще можно выделить визуально классы, то упорядоченная матрица такого размера практически не поддается восприятию.
Но именно в экономике, где число объектов редко превосходит сотню, такой анализ наиболее пригоден. Конечно, если требуется решать не исследовательскую, а производственную задачу с частой повторяемостью и невозможностью участия человека, надо использовать другие алгоритмы. Но даже и их результаты рекомендуется получать не в форме простого распределения объектов, по классам, а в виде блочной матрицы (см.
табл. 5. ! ) . Примеры использования алгоритмов диагонализации даны в 3.3, 4.3, 4.4. Эталонные алгоритмы. В настоящее время процедуры эталонного типа наиболее универсальны для решения задач классификации. Это связано со следующими обстоятельствами: алгоритмы быстры 74 и удобны в вычислительном отношении; позволяют добиться локальных экстремумов некоторых показателей качества н наилучшим образом реализовать представления о качестве классификации, используя параметрьг разных типов. Для проведения эталонной классификации надо принять трн решения: обосновать тнп задаваемых параметров и их конкретные значения (начальные нли конечные); выбрать способ первичного задания эталонных множеств; найти способ корректировки классов и стабилизации в целом.
Эталонные процедуры, если рассматривать их независимо, могут в комбинациях образовать большое число алгоритмов, превышающее количество описанных в табл. 2.3. Вопросы, связанные с заданием параметров, обсуждаются в ЗХ 9.г У Выбор начальных условий очень важен для работы всех эталонных процедур. В принципе они сходятся при любых условиях, но приводят к различным результатам (см. 2.4).
Поэтому ряд процедур представляет собой не способы классификации, а приемы выбора эталонов (см. алг. 45 — 48, 63). Основных способов пересчета эталонов и получения классификации четыре: прямое распределение объектов по классам без стабилизации процесса (алг. 33); параллельное распределение объектов по всем эталонным множествам (алг. 39); последовательное распределение объектов одного класса (алг. 40); последовательно-параллельное распределение объектов и стабилизация процесса (алг. 4!). Последний способ, как ясамый нтерирующий», предпочтителен в смысле минимизации возможности случайных возмущений. Если его соединить с различными из перечисленных способов, можно получить целый спектр новых алгоритмов.
Процедуры эталонного типа вполне пригодны для обработки больших массивов информации и вызывают в последнее время пристальный интерес специалистов [29, 129 и др.]. Обсуждение возникающих вопросов тесно связано с оптимизационным направлением в классификации и будет частично предпринято в 2.3. Алгоритмы типа разрезания графа. Процедуры в своем большинстве трудоемкие, для больших массивов малопригодные (за исключением способов случайного разрезания (алг.
56); обсуждение см. в разделе об иерархических процедурах [59]). Эти алгоритмы обладают двумя свойствами: возможностью визуализации н выделения кластеров сложной, в том числе невыпуклой, формы. В целом проблематика разрезания графа в смысле некоторых оптимизационных требований является специфическим направлением теории графов и выходит за рамки книги.
Некоторые интересные приложения к задаче классификации обсуждаются в [26, 59 и др.]. Прочие процедуры кластер-анализа достаточно подробно рассмотрены в тексте. В заключение отметим следующее: все алгоритмы, кроме 16 (см. также табл. 2.4), рассматривают объекты как единичные, 75 невзвешенные точки.
В алг. 16 вводятся «массы» точек, но скорее из формальных соображений общности. Однако проблема взвешивания объектов в статистике, особенно экономической, весьма актуальна. Практически все средние величины относительных показателей (производительности труда и пр.) определяются как взвешенные, причем весами выступают некоторые абсолютные показатели (численность, объем продукции и др.), т. е. веса имеют совершенно ясный экономический смысл, который полезно учитывать при классификации.
Но как определить веса у объектов в многомерной ситуации, когда по каждому из показателей они имеют разное значение? Задача определения оптимальной системы взвешивания при 'многих показателях с целью сохранения наилучшим образом при многомерных расчетах (корреляцня и т. д.) важнейших одномерных характеристик — средней дисперсии — обсуждалась ранее'. В качестве решения предлагалось усреднить удельные веса показателей на объекте. Поставим задачу более точно: если все показатели измерены в шкале отношений, то критерий качества имеет вид: минимизировать сумму относительных отклонений истинных средних от оптимально взвешенной при ограничении на сумму весов (равной 1). Методом множителей Лагранжа получаем систему из и уравнений, решение которой даст оптимальные веса.
Классификация с учетом весов существенно повысит экономическую обоснованность расчетов; скажем, крупные заводы сразу будут задавать центры кластеризации, что экономически оправдано. 2.3. АЛГОРИТМЫ ОПТИМИЗАЦИИ И АППРОКСИМАЦИИ 2.2Л. РАЗВИТИЕ ИДЕЙ Рассмотрим точные методы решения задачи кластеризации. Точность здесь понимается лишь в одном смысле: исследователь считает, что ему удается свои представлении о классификации выразить не в терминах некоторых желательных свойств кластеров, совокупности в целом или самого процесса построения групп, как это делается в 2.2, а в виде задания определенной функции, экстремум которой иа множестве разбиений удовлетворяет его суждению о хорошем качестве разбиения. Если попытки непосредственно решать задачу классификации формальнымн методами восходят к началу нашего века, то точные постановки появились в 50-х годах.
Статья Т. Далениуса «Проблема оптимальной стратнфикании» вышла в 1951 г. и содержала формулировку критерия минимизации анутринластерной дисперсии и алгоритм (типа й-средних) поиска оптимального решения (см 1131, р. 106]). Авторы алгоритма «вроцлавской таксономии» (1951) также говорили о поиске такого разрезания КНП, чтобы сумма внутрикластериых ребер была минимальной (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
