И.Д. Мандель - Кластерный анализ (1185344), страница 23
Текст из файла (страница 23)
В [79] предлагается способ оптимизации критерия Раж основанный на том, что используемая функция обладает свойством так называемой супермодулярности. Это позволяет для ее оптимизации использовать развитую теорию метода последовательных расчетов В. П. Черенина, который интенсивно используется в задачах дискретной оптимизации. Видимо, можно и другие критерии проверять на наличие супермодулярности и использовать в случае успеха точные алгоритмы.
Метод ветвей и границ минимизирует Р,в. Третье направление в точном решении задач классификации связано с недавно сформированной, но бурно развивающейся теорией монотонных систем [23, с. 29 — 34 и др.']. Упрощая понятие, дадим следующее определение: монотонной системой называется . множество объектов, такое, что если из него изъять объект, то некоторая функция, определенная на любом подмножестве множества, не возрастет на любом подмножестве. Приведем удобный пример: йа каждом объекте определена функция, ставящая ему в соответствие сумму расстояний от данного объекта до всех остальных; очевидно, что изъятие любого объекта может привести только к невозрастанию суммы расстояний для каждого объекта и для любого их подмножества.
Оказывается, в таких ситуациях можно строить точные и чрезвычайно быстрые алгоритмы оптимизации некоторым образом устроенных функционалов; нх трудоемкость не превышает О(А1а), тогда как для перечисленных выше методов точного решения она может доходить до экспонеициальной величины полного перебора. Правда, функционалы этн весьма специфичны.
Так, для описанной системы с помощью построенного критерия можно выделять классы, расположенные как бы на концентрических сферах относительно центра множества; например, хорошо разделяются классы Е и Р на рис. 2.1. Более традиционные функционалы в духе табл. 2.5 для монотонных систем пока не разработаны. Можно, однако, использовать комбини- ' Автор выражает признательность Е. П. Кузнецову и И. Б. Мучнику за обсужпение втой проблематики. 100 рованные алгоритмы — с помощью упомянутого функционала строить множество максимально удаленных точек — ядро, а затем, считая их центрами классов, проводить классификацию одним из эталонных алгоритмов.
Такой способ первичного задания эталонов, как легко видеть, является обобщением эвристических процедур 45 и 46 из 2.2. Алгоритмы точной оптимизации, за исключением процедур, связанных с монотонными системами, в силу своей высокой трудоемкости могут решать задачи размерностью не более нескольких десятков, от силы 2 — 3 сотен объектов. Иногда такие решения могут бйть практически весьма полезны, но чаще всего точные значения функционалов для конечных целей исследования нужны достаточно условно, о чем подробно говорилось в 2.2. Однако дальнейшие исследования по быстрым и точным методам классификации, бесспорно, имеют большое значение хотя бы как способ решения целого ряда теоретических проблем — о значимости отдельных функционалов для человека, о степени приближения нестрогих методов оптимизации и т.
д. В закпючение отметим следующее. Все рассматриваемые в параграфе критерии определяли задачу безусловной одномерной оптимизации. Однако вполне возможны естественные обобщения, вплоть до решения задачи векторной оптимизации при наличии ограничений. Ограничения могут быть различны — на степень заполненности классов, на степень связи в них и т. д. В известной мере они уже учтены в тех функционалах, где фигурируют задаваемые жестко пороги. Однако в общем случае многокритериальные задачи с ограничениями пока не нашли широкого применения (см. обсуждение и библиографию в (29, с.
53 — 64) ). 2.3Л. АППРОКСИМАЦИОННЫЙ ПОДХОД В КЛАСТЕРНОМ АНАЛИЗЕ Все рассмотренные выше функционалы качества классификации ориентированы на решение одной задачи: в явном виде эксплицировать представление о хорошей классификации в целом (т. е. не на уровне свойств отдельных кластеров). Как видно, таких представлений существует очень много. Но имеются некоторые соображения универсального характера, которые учитывают лишь самые общие черты классификации.
Например, если требуется получить разбиение без пересекающихся классов, то просто фиксируется, что искомое отношение является отношением эквивалентности (см. 1.2); можно потребовать, чтобы результирующее отношение представляло собой иерархическое дерево и т. д. Если обозначить искомое отношение произвольного типа через У, исходные данные через Х, а оператор перехода от Х и У вЂ” через Р (пока не конкретизируя вид этих конструкций), то в общем случае возникает естественный функционал, отражающий стремление мак- 101 симально приблизить результирующее отношение к имеющимся данным: [[У вЂ” РХ[[- ппп, где [[А[[ — какая-либо норма, Задачи такого типа — аппроксимация «плохо устроенного» множества Х и «хорошо устроенной структурой» У вЂ” давно известны в математике и имеют множество приложений (в теории устойчивых решений некорректных задач, в задачах оптимального управления и т.
д.). В статистике самым распространенным типом является задача построения регрессии, где Х вЂ” вещественная матрица, У— вектор результатного показателя,[[А[[ обычно принимается квадрат.ной функцией (в методе наименьших квадратов). Применительно к проблеме класснфнкацнн аппрокснмацнонный подход имеет прнмерно 15-летнюю историю, хотя некоторые предвосхищающие идеи были выдвннуты ранее. Первые постановки, обсуждавшнеся в работах Т. Зана (1964), Г.
Вейнера (1971) н др. (см. [62) ), заключались в следующем: найти отношение эквнвалентаостн, оанболее блнзкое к походному произвольному бнпарному отношенню с булевской матрнцей. Увязка такой постановкн (часто независимо от ранних работ) с проблематикой анализа данных была осуществлена в трудах С. Ренье (1965), Б. Миркина (1969), А. Ляпунова (1972), Г. Фридмана (1973) н других последователей (см. [61[). Прн этом по-прежнему речь шла о качественной ситуации: исходные данные представлялись как граф сходства с непомеченными ребрами (это достнгалось, например, введением порога существенностн для мер близости), а требуемое разбненне задавалось как зквнвалентность, т.
е. булевская матрица «объеьь объект> аппрокснмнровалась такой же матрнцей, полученной как развертывание номинального признака (см. 1.2). Аналогичная постановка для результирующего разбиения нерзрхнческого типа была сделана С. Джонсоном в 1967 г. [33, 13Ц (предполагалосгь что наилучшее нерархнческое разбненне должно нметь макснмальную ранговую корреляцню с упорядоченными расстояниями исходных данных).
Эта работа, как н статья того же года [136), положнла начало целому направлению в построеннн оптимальных в различных смыслах нерархнческнх деревьев [120, 122 н др.[. Идея макснмнзацнн корреляции между «обычным» разбиением н матрнцей расстояний была использована Г. Мнллнганом (1980) для своего критерия качества классификации (см.
гзз), хотя еще раньше почти такая же велнчнна рассматрнвалась нз модельных более общих соображеннй в [61). В 1974 — 1976 гг, в статьях И. Мучннка, Л. Бородкнна, В. Куперштоха, Б. Мнркина, В. Трофимова была поставлена в разных формах задача непосредственной аппроксимации матрицы связей некоторыми матрицами, без перевода исходной матрнцы в качественную форму [61). Впоследствии задача была подробно изучена н легла в основу создання так называемого качественного факторного анализа [62). Похожие соображения лежали в основе концепции так называемых адднтнвных кластеров, разрабатываемой начиная с середины 70-х годов П.
Араби, Дж. Керролом, Р. Шепардом н др. Подробное сопоставление двух подходов н обоснованне большей конструктивности первого было сделано в [143[. Наконец, в 1981 †19 гг. появляются работы Б. Миркина н И. Мучннка, впоследствии развнтые в [63[ о задачах аппроксимации, где в качестве Х выступают не квадратные матрицы «объект-объект>, а прямоугольные «объект-прнзнак>, т.
е. собственно матрнцы исходных данных [16, 63). Основные направления аппроксимационного подхода в задаче классификации объектов подробно изложены в доступной литературе [6[ — 63, 99 и др.], где можно найти детальную библиографию упо- 102 мянутых выше и многих других работ. Наиболее полное описание подхода применительно к задаче классификации содержится в [63). Поэтому мы не будем здесь стремиться к изложению всей развет-' вленной концепции аппроксимацнонных задач, остановимся лишь на идейной стороне двух наиболее интересных, на наш взгляд, вопросов.
А именно, рассмотрим результаты прямой аппроксимации матрицы связи исходной таблицы «объект-прнзнак», ориентируясь главным образом на [62, 63). Задача аллроксимации матрицы связей. Пусть имеется матрица связи А=[он[я„„, где связь тем сильнее, чем больше ац (см.
!.3). Требуется найти такое разбиение' с булевской матрицей 1?=[ги[нх ю которое бы в наибольшей мере соответствовало А. Элементы гц определяются, как в (1.1): гл=1, если объекты в одном классе, 0 — если в разных. Как сопоставить А и ?? друг с другом? Ведь в А — вещественные числа, а в т? — булевы переменные. В [61] предложено взвешивать т?, вводя некоторые коэффициенты масштаба Л и сдвига )х.
Тогда критерий аппроксимации будет иметь вид: Ь(й, х, н)= ')Р (о! — Хги — н) — пнн. (2.3) 1,! 1 Минимизацию Л(г, Л, р) надо производить сразу по трем неизвестным величинам — скалярам Л, )ь и матрице ??. Для аналитического изучения (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}
