автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Анализ и описание нечисловых данных подмножествами

Российская Академия наук г . ^Цн^титут проблем передачи информации

ГСП'* ^ .о и;

На правах рукописи ГЕНКИН АЛЕКСАНДР ВЕНИАМИНОВИЧ АНАЛИЗ И ОПИСАНИЕ НЕЧИСЛОВЫХ ДАННЫХ ПОДМНОЖЕСТВАМИ

Специальность 05. 13. 17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1995

Работа выполнена в Институте проблем передачи информации РАН

Научные руководители:

доктор технических наук, профессор В. В. Зяблов

кандидат технических наук

И. Б. Мучник

Официальные оппоненты:

доктор физико-математических наук А. В. Налишевсккй

кандидат технических наук"

В. В. Максимов

Ведущая организация

Всероссийский институт научной и технической информации Миннауки РФ и РАН

Заюгга состоится " "_ 1995 г. в_час. _мин.

на заседании диссертационного совета Л- 003. 29. 01 при Институте проблем передачи информации РАН по адресу: 101447 Москва, Б. Каретный пёр. ,19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАБ.

Автореферат разослан " '_ 1995 г.

Ученый секретарь Диссертационного совета Д. 003.29.01 доктор технических наук, профессор

Степанов С. Н.

Актуальность темы. Существенную роль в анализе ванных, описывающих слабоформализованные процессы и системы, играет задачи, в которых "ответ ищется не в виде чисел или совокупностей чисел (векторов, матриц), а в виде конечных множеств или их наборов. С одной стороны, это:объясняется тем. что сами данные представлены в виде значений переменных, значительная часть которых измерена в конечных нечисловых икалах. С другой стороны, результаты дойны восприниматься и интерпретироваться специалистом предметной области, интегрироваться в базы профессиональных знаний, что требует их представления в логическом виде. Последнее обстоятельство особенно существенно при построении партнерских систем (В. С. Переверзев-Орлов).

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

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

1. Поиск кластеров, описываемых малым числом переменных.

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

3. Поиск набора симптомов для порогового синдрома.

4. Поиск набора частных решателей для систем распознавания, основанных на голосовании.

5. Поиск диагностического решения в модели Пенга-Редхиа.

Задачи 1 и 2 обладают рядом свойств, затрудняюяих ах решение

: опорой на принятые представления о кластерах: искомые подыно-

- г -

жества могут пересекаться и не обязательно должны покрывать все рассматриваемое мнохество; отсутствует априорное знание о числе или масштабе кластеров. Для задач 3, 4 и 5 кластерная интерпретация вообще неадекватна. Во всех задачах недостаточно рассмотрения попарных взаимодействий.

^ В работе предлагается подход, основанный на явном формулировании искомых свойств подмножеств, причем упор», делается на свойства отдельного подннохества. Свойства набора подмнохеств, в частности такие как свойство образовывать разбиение, рассматриваются как вторичные. Подход основан на мерах связи типа элемент - мнохество: для каждого элемента х и подмножества а конечного множества и мера связи определяется числовой, функцией л (х,а) (для краткости - я-функцией). В качестве модели подннохества, которое дол-хно послухить результатом анализа данных в задачах типа рассмотренных выше и родственных им, вводится понятие ь-устойчивого мно-хества - такого подннохества а, что: (1а) п(х,А)<с, для любого х, принадлежащего а

(16) я(x,A)>t, для любого х, не принадлехадего а

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

Цель исследования состоит в:

- разработке методов анализа данных, обеспечивающих построение подмнохеств конечного множества с заданными свойствами;

- разработке эффективных алгоритмов анализа данных указанного класса.

Научная новизна работы.

1. Введено понятие с-устойчквого подмножества, которое предлагается в качестве модели искомого подмножества для задач анализа данных.. Выделены классы я-функций, для которых ^устойчивые мно-хества существуют при любом с, и изучены свойства этих множеств: взаимное положение и изменение в зависимости от параметра ^ Установлена связь с ядрами монотонных систем. Основные понятия"теории монотонных систем перенесены на конечные частично-упорядоченные множества.

2. Задача построения набора частных решателей для голосования приведена к максимизации субмодулярной функции. Предлохен путь максимизации - метод распределенного доучивания.

3. Построен оптимальный алгоритм поиска максимума субмодулярной функции и вычислена функция Шеннона для этой задачи.

4. Построено обобщение иерархического кластерного анализа, допускающее, кластеры, пересекавшиеся на одном уровне, и неполные классификации.

Положения, выносимые на защиту:

- метод построения набора частных решателей для распознавания;

- обобиенный иерархический кластер-анализ;

--оптимальный алгоритм поиска максимума субмодулярной функции.

Теоретическая и практическая значимость. В работе показано, . что ряд методов и практических задач анализа представимы в виде поиска «^устойчивых подмножеств конечного множества, в частности -поиска максимума субмодулярной функции.

Предложена модель выбора множества частных решателей, приводящая к максимизации субмодулярной функции множества. При различном выборе параметров модель позволяет строить наборы решателей для схем распознавания, основанных на голосовании, или для кон-цептуальнЬго кластер-анализа. 'Предложей эвристический Алгоритм" максимизации, работающий параллельно с поиском решателей, и интерпретируемый как распределенный вариант классического доучивания.

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

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

Построен оптимальный алгоритм поиска максимума субмодулярной функции и другие алгоритмы поиска с-устойчивых множеств.

\

Апробация рабЬты- Отдельные результаты работы докладывались на .1 и Всесоюзной иколе-семинаре. "Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание"

(Одесса, 1990г), Всесоюзном научно-техническом симпозиуме с международным участием-"Теория и практика классификации и систематики в народном хозяйстве" (Пущино, 1990г.), семинаре "Сложность алгоритмов" МЙАН и ВЦ АН СССР (1991г.), семинаре "Дискретная оптимизация" ИПНТП АН СССР (1991г.).

Публикации. По теме диссертации опублико'вано 8 работ.

Структура работы. Работа состоит из введения, 3 глав и заключения. Список литературы включает 61 наименование.

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

1. Поиск кластеров,' описываемых малым числом переменных. В сложных задачах клинической медицины данные, необходимые^для принятия решения, включают большое число переменных, зачастую исчисляемых сотнями. Число наблюдений при этом редко превышает несколько десятков. Сократить число переменных без существенной потери информации не удается. Однако можно надеяться на'существование подмножеств наблюдений, описываемых каждое небольшим числом переменных, существенных именно для данного подмножества. Основанием для надежды служит существующая в медицине культура мышления и объяснения, где каждый случай - индивидуальный или типичный - описывается ограниченным набором характеристик, существенных именно для этого случая. Близкая задача формулировалась В. Е. Левитом.

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

3. Поиск набора симптомов для порогового синдрома. Решения в медицине хорово описываются сетями простых пороговых элементов,

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

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

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

- каждый решатель должен давать правильное решение на значительном числе примеров и ошибаться на небольшом числв примеров;

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

дехнее, если таких решателей несколько;

- число решателей, дающих правильное решение, для разных примеров не должно слишком сильно различаться;

- общее число решателей ограничено.

Задача сформулирована М. М. Бонгардом применительно к алгоритму Кора;, изучалась М. П. Поляковой и М. Н. Вайнцвайгом.

5. Поиск диагностического решения в модели Пенга-Редхиа. Мо-

Ч

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

Перечисленные задачи обладают рядом свойств, затрудняющих их решение с опорой на принятые представления о кластерах:

- искомые подмножества могут пересекаться; при этом пересечения могут быть весьма существенными. Минимизация пересечений, которая иногда предлагается в качестве ослабления запрета на пересечения, едва ли адекватна смыслу задач из примеров 1 и 4;

- искомые подмнохества не обязательно должны покрывать все рассматриваемое мнохество; вместе с предыдущим свойством это делает неадекватным стандартное понимание кластеров как образующих разбиение.. Более того, задачи .из примеров 3, 4 и 5 _требувт нахождения одного подмнохества, а не какой-либо их совокупности;

- отсутствует априорное знание (хотя бы приблизительное) о числе или масштабе кластеров, которое необходимо для применения итеративных методов кластерного анализа (Форель, Изодейта, метод динамических сгущений и др.);

- особенно вахно: во всех приведенных примерах недостаточно рассмотрения попарных взаимодействий. Многие методы кластерного анализа, в тон числе практически все иерархические методы, если не предполагают структуры•евклидова пространства, то опираются на меру удаленности (или близости) мехду эленентами рассматриваемого мнохества. Приведенные примеры требуют учета взаимодействий более высоких порядков.

Предлагается подход, основанный на мерах связи типа элемент -мнохество. Для каждого элемента х и подмножества л конечного мнохества а мера сйязи определяется числовой функцией я (х,а> (для < краткости * я-функцией). Наиболее частая (хотя не единственная) интерпретация - мера удаленности или отличия х от а. Такие меры могут быть, например, получены исходя из шгроко применямых в ана-

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

В качестве модели искомого подмножества предлагается понятие «¡-устойчивого мпожества. Название объясняется тем, что подмножества, удовлетворяющее (1а,б), и только они, являются неподвижными точками преобразования

(2) - А.-► V (А) = { х£0: Я(х,А)<Ь }

В случаях когда уместна кластерная интерпретация, они. называются также ¡¡-кластерами. В этом случае (1а) выражает свойство кластера быть компактным, а (16) - свойство быть изолированным.

Далее во Введении кратко излагается содержание отдельных глав и полученные результаты.

Первая глава посвящена теоретическому анализу понятия ^устойчивого множества: изучается вопрос о существовании ^устойчивых множеств и связь с теорией монотонных систем. В §1. 1 выделены классы эт-функций, для которых существование «¡-устойчивых множеств гарантировано при любом V. поряшсово-однородные, суммируйте, ультраметрические, невозрастающие. Два из этих классов - суммируемые и ультраметрические - находят приложения в анализе данных и подробно изучаются в дальнейших разделах работы.

я-функция называется- порядково-однородной, если для всех х,уеи. А,А'яп имеет место: л (х,А)<л (у,А) тогда и только тогда, когда я (х,а' )<я (у,а' ).

я-фуккция называется суммируемой, если она представляется в виде разности для некоторой подходящей функции множества £(А):

(3) Я (х, А) = £ »их) - £(А-х),

Тогда минимумы функций вида ? (А)=£(А)-с- |л| оказываются «¡-устойчивыми множествами я (х,А).

Ультраметрическими называются я-функции, удовлетворяющие для любых хед, уеп-А, леи неравенству

(4) 1Г£х,диу; < пах ( Я (X,А) , ТГ (у,А))

а также развязанные^4^ (х,АИх) = я(х,А1. Название дано по аналогии с ультраметрическим неравенством для расстояний.. Смысл этого требования - в возможности посладовательного поиска г-устойчивых мно-

хеств: если для некоторого множества выполнено (1а), то можно добавлять к нему элементы, нарушающие (16). В силу ультраметрического неравенства, (1а) при этом сохраняется, и благодаря конечности будет достигнуто t-устойчивое множество.

Ультраметрические функции помогают построить обобщение иерархического кластер-анализа, допускающее пересечения кластеров на одном уровне и неполные классификации. Ряд известных кластерных методов удается естественно описать в терминах^эбобщенного иерар- . хического кластер-анализа. Кроме того, на его основе предлагаются подходы к ревению задач 1 и 2, приведенных выше. Этому посвящена глава 3 работы.

. В §1.2 рассматриваются с-устойчивые множества монотонных jr-функций. я-функция называется неубывающей (невозрастающей) если из asa' следует я (х,а)<п (х,а'1 (соответственно, я (х,а)>я (х,а' ;) для любых a,a'sd, хеи. Оказывается, что для неубывающих функций е-устойчивые множества не вложены друг в друга при одном t; если хе одно устойчивое множество вложено в другое, то большему из них соответствует большее значение t. Это свойство важно для иерархической кластерной интерпретации.

Далее устанавливаются связи с теорией монотонных систем, где . неубывающие я-функции изучаются в связи с порохдаемыми ими по формуле Муллата функциями множества .. . . . ...

(5) F(A) = min Я(х,А)

х£А

Эти функции квазивогнуты, т.е. для них имеет место неравенство:

(6) FÍAUb; > min (F(A), F(B))

Известен и способ построения ir-функции по функции множества -формула Маливевского:

(?) Л(Х,А) = max {F(S) :x£SZAUX}

В работе показано, что формулы (5) и (7) задают соответствие Галуа между между естественно упорядоченными множествами функций множества и неубывающих ir-функций. При этом выявляется особая роль ультраыетрических я-функций: среди всех неубывающих, порождающих данную квазивогнутув, ультраметрическая является наименьшей. Кроме того, в ультраметрическом случае обычно квадратичный алгоритм нахождения наибольшего по вложению максимума квазивогнутой функшга (т. н. наибольшего ядра) упрощается до линейного.

В ультраметрическом случае t-устойчквые множества могут быть охарактеризованы через квазивогнутые функции: oim суть все максимальные подмножества, не содержащие подмножеств А таких, что f (а) > с.' Для остальных неубывающих jr-функций верно менее сильное

утверждение: t-устойчивые множества не содержат подмножеств а таких, что F(A)>t. Если в качестве я (х, AS выступает мера удаленности или различия, то эти факты имеют естественную интерпретацию в терминах кластерного анализа. По определению F (А), такие подмножества А, что F(А)>с, могут интерпретироваться как разреженные. Тогда t-устойчивые множества суть те, которые не содержат разреженных подмножеств.

Далее рассматриваются невозрастающие jr-функции и связанные с

ними квазивыпуклые функции множества: F(А)=тах я (x,AJ.

xsa

t-устойчивые множества образуют решетку, единицей которой является наибольший по вложению минимум fía), а нулем - наибольший по вложению максимум квазивогнутой функции, порождаемой неубывающей функцией, я' (х,А)-п (х,0-А).

Для невозрастающей я-функции преобразование (2) оказывается изотонным. Обратно, по любому изотопному преобразованию можно по- ' строить невозрастающую я-функцию:

г о, если xgv(A)

Я<Х,А) = •[ 1( если xgvfji)

Эта связь помогает перенести основные результаты теории монотонных систем на конечные частично-упорядоченные множества с нулем и единицей, что проделано в §1.3. Указаны возможные пути применения результатов в кластерном анализе.

Во второй главе ряд задач анализа данных сводятся к максимизации субмодулярных функций, а также рассматриваются алгоритмы поиска максимума таких функций. Пусть я (х,А) - суммируемая, и представляется в виде разности функции множества f (А). Тогда л(х,д) является неубывающей (невозрастающей) если и только если f(а; - супермодулярная (субмодулярная), т.е. для любых а, в:

£ (AUbí +f (АПВ) >f!A) +f (В) ( f (A\JB) +f (АПВ) <f (A) +f (B1 >

Как показано в главе 1, локальные минимумы функций вида f' (A)=f (A) -t- 1а| суть t-устойчивые множества я 1х,А). Поэтому если я (х,А) - неубывающая и суммируемая, то локальные максимумы еэ субмодулярной суммы суть локальные минимумы супермодулярной Функции -f(A), или t-устойчивые множества -я (х,а).

В §2. 1 строится формализация задачи 4 - о построении набора частных решателей Xприводящая к максимизации субмодулярной (минимизации супермодулярной) функции множества. Полагаем, что каждый частный решатель умеет относить объекты лишь к какому-то одному классу - иначе будем рассматривать его как несколько частных реша-

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

При поиске частных решателей каждому из них предъявляются требования-чувствительности и специфичности 1 (чувствительностью решателя, призванного голосовать за некоторый класс, называется вероятность того, что решатель сработает на объекте этого класса; специфичностью называется вероятность того, что решатель не сработает на объекте другого класса). Для каждого примера из обучающей выборки число решателей, характеризующих этот пример и относящих его к тому классу, к которому он в действительности принадлежит, •назовем обученностью набора решателей на этом примере. В случае "чистых" решающих правил, не делающих ошибок.на обучающей выборке, число решателей, характеризующих пример, и есть обученность. М. М. Бонгард отмечал, что для повышения надежности узнавания частные решатели должны, во-первых, характеризовать все обучающие примеры, и во-вторых, число примеров с обученностью существенно ниже средней (т.н. отстающих) должно быть минимально.

Для случая "чистых" решателей каждому из них поставим в соответствие подмножество примеров обучающей выборки, которые он характеризует.. .Обозначим.: и-, множество обучающих, примеров некоторого класса; s - набор решателей, голосующих за этот класс; N(x,S) -число решателей из набора s, характеризующих пример х. Задачу построения-набора решателей формализуем в виде:

где первый член выражает качество обучения, второй - штраф за число решателей, включенных в набор; с - штрафной коэффициент; <р (г) -числовая функция, по смыслу задачи монотонно возрастающая. Чтобы обеспечить равномерность числа голосов по примерам и уменьшить число "отстающих", потребуем, чтобы приращение первого члена функционала (8) было больше в тех случаях, когда добавляемый решатель характеризует примеры с меньшей обученностью. Пусть для простоты добавляется решатель, который характеризует ровно один пример: А-Сх^). Тогда приращение имеет вид:

ЯССхо1,Б) - <((1!(хо,Б) + 1) 'Сформулированное требование означает, что <? - функция с убывающими приращениями, т. е. вогнутая. Показывается, что в этом случае л (А,Я) - убывающая, откуда немедленно следует,, что функционал в

(8)

(8) - субмодулярный.

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

Ограничимся случаем двух классов, представленных в обучении множествами примеров соответственно а^ и иг; О^Пп^и. Отбирая решатели за первый класс, будем считать, что решатель празильно характеризует примеры из первого класса, на которых он срабатывает, и примеры второго класса, на которых он не срабатывает. Тогда (8) принимает вид:

Г * Т (\■s^-N(x,s)) - с|£| —»

1 г

а разность функционала примет вид:

- £ Ь(п(х,3)) * [ Ь(Я(х,В)} - с хелЛи хеи -а

1 г

Очевидно, это также субмодулярная задача.

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

Чувствительность решателя, призванного голосовать за некоторый класс, оценивается на обучающей^выборке долей примеров этого класса, на которых решатель срабатывает. Фактически в ходе перебора считаются не доли, а сами количества примеров, поскольку знаменатели постоянны. В простейшем случае эти значения сравниваются с порогами, заданными в качестве параметров алгоритма.

Приращение функционала из (8) при добавлении решателя А к текущему множеству решателей б можно представить в виде:

ЯГА,Я} - У Ъ(я(х,Б)) - г х£а

где: б (г+1)-<р (г). Если в цикле, поиска очередного решателя не

обращать внимания на константу t, то это выражение оказывается похоже на оценку чувствительности: вместо числа элементов во множестве А имеем сумму весов этих элементов. Предлагаемая процедура сводится к тону, чтобы в ходе переборного поиска решателей заменить оценку чувствительности на приращение функционала h(a,s). оставив оценку специфичности без изменений. Для упрощения вычислений следует каждый раз при включении очередного решателя а в набор пересчитывать текущие веса примеров В(N(x,Sl) для всех х£А.

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

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

.Функционал (8) находит еще одно применение в анализе нечисловых данных» когда погнутая функция <pfe; -. не монотонно возрастающая, а имеет единственный максимум в точке z=i. Тогда Г ф (n(x,s) )

х&а

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

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

экспертом, как это происходит при построении-партнерских систем.

Реализация концептуального кластер-анализа с необходимостью должна использовать подалгоритм, который обеспечит выбор' среди понятий - кандидатов такого их подмножества, чтобы соответствующие области приближались к разбиению всего множества объектов. В качестве этого подалгоритма мы и предлагаем максимизацию функционала (8), где ч> (г) - вогнутая функция с максимумом в точке г=1. Использование точных или приближенных методов субмодулярной максимизации даст гарантированную оценку трудоемкости алгоритма, отсутствующую в случае эвристического поиска, предлагаемого обычно в работах по концептуальному кластер-анализу.

В §2.2 рассматривается задача 5 - поиск диагностического ре- ■ шения в модели Пенга-Реджиа. Показано, что поиск максимума сформулированного там функционала правдоподобия можно свести к максимизации субмодулярной функции. Это позволяет применить для решения . оптимальный метод из §2. 3.

В §2. 3 предлагается метод поиска максимума субмодулярной функции и доказывается его оптимальность по Шеннону, т.е. в следующем смысле. Предполагается, что функция задана процедурой вычисления еэ значения на любом подмножестве. Подсчитывается, сколько раз алгоритм поиска максимума обращается к этой процедуре. Оптимальный алгоритм обеспечивает минимальное число" обращений в худшем случае при данной мощности множества. Это число оказывается равным сумме трех наибольших биномиальных коэффициентов в ряду , где л - мощность всего множества, к=1,...,п.

Множество а называется подъемом функции £, если £(А) > £(А-{х}> для всех хед, и соответственно спуском, если

£(А) > £(А\}{х}) для всех хеи-А Показано, что среди множеств, на которых достигается максимум функции, найдется множество, являющееся одновременно подъемом и спуском.

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

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

- кластеры, описываемые небольшим числом переменных из всех наблюдаемых переменных (остальные переценные - несуяественные);

- кластеры, приближенно описываемые линейной моделью.

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

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

В §3. 1 строится понятие обобщенной иерархии. Обычный иерархический кластер-анализ строит совокупность кластеров, образующих дерево по вложению, с соответствующими им. значениями меры удаленности (различия), возрастающими по уровням иерархии. Эта структура полностью описывается ультраметрикой с1 , х,уеи, - кластеры уровня ь определяются как подмножества ас с/ такие, что: (9а) а < с- для всех х,уел,

(96) а > t для всех х£А, уеп-А .

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

- кластеры попарно не пересекаются.

- кластеры образуют покрытие V, т. е. каждый элемент и принадлежит какому-то кластеру. '

В случае обобщенной иерархии они заменяются более слабым свойством: ...

- кластеры не являются подмножествами друг друга.

Доказывается, что если функция я (х,А) - неубывающая, с неотрицательными значениями и ультраметрическая, то ее е-кластеры с соот-. ветствующими значениями с образуют обобщенную иерархию. При этом я (х,А1 замещает а , а условия (1а,б) замещают (9а.б).

Обычная иерархия, естественно, является частным случаем обобщенной. Формулируются Необходимые и достаточные условия' на я-функшш, гарантирующие непересечение кластеров на одном уровне иерархии, а таете необходимые и достаточные условия, гарантирующие покрытие кластерами всего кластеризуемого мнохества, начиная с некоторого уровня иерархии.

В §3. 2 показано, каким образом обобщенная иерархий позволяет описывать известные кластерные методы, а такхе порохдать новые полезные процедуры. Рассматривается ряд известных кластерных методов, основанных на понятиях теории графов. Для их описания вводятся функции "условной удаленности" д(у,х,А), где х,уелси, удовлет- . воряющие следующим требованиям: д(х,у,А) = д(у,х,А) , если аса', то д(х,у,А) > д(х,у,А') . Тогда следующая функция оказывается ультраметрической:

Я (х,А> - тах д(х,у,А) . у€а

Для уровневых. графов, порожденных матрицей различий на- мнохестве • и, в качестве функций д рассматриваются: минимальный уровень, обеспечивающий существование к вершинно-непересекающихся, к ребер-но-непересекаюшихся путей мехду вершинами х и у в подграфе а; различие мехду ними при мощности а более к; минимальный уровень, обеспечивающий существование пути мехду х и у длины не более г с промежуточными элементами из а или из а. Таким образом получаются методы: сильной к-связи, Тс-перекрывающий, метод ¿-клики, прямой и непрямой методы классификации по г-диаметру. Определяя я(х,а; как минимальный уровень, при котором вершина х в подграфе а имеет степень не меньше к, получим метод слаЬой к-связи. В качестве частных случаев получаются кластерные методы блихайаего соседа и клики.

Для задачи 1 - о кластерах, описываемых малым числом переменных - предположим, что даны ¿-мерные наблюдения: х=<х',___,х">, и

на шкале каждой переменной задана мера удаленности й' (х1,у1), д=1,..,к. Диапазоны изменения мер по разным переменный должны быть согласованы между собой. Определим:

Я(х,А) - £ <р( (Нага1 (А\1х) ] ,

1» I ^ '

dia»' (A) = max dl (x',yl ) x,y£A

где (p - монотонно возраставшая вогнутая числовая функция. Например,- мохно взять ее в виде ip fz)=czd с параметрами с> О,- о«и<1. Построенная я-функция является неубывающей и ультраметрической. Если а - t-кластер, то на очередном шаге построения обобщенной .иерархии ищется уеи-А, дающий минимум приращению

^ | ip^dian' WUy;| - <p|tíiara'fAjj j

Пусть для примера у такой, что в одинаковой мере выходит за пределы диапазона а по двум переменным i и j:

diam' fA'Jy) - diam' (A) = <¡í.amJ (Ally) - di"amJ (A)

По вогнутости 9, то измерение, по которому а имеет больший диаметр, даст меньший вклад в приведенную выие сумму. Поэтому если в какой-то момент построен t-кластер с неравными размерами по разным осям, то неравномерность эта будет иметь тенденцию к нарастанию: последующие t-кластеры (при нарастании t) будут все .более вытягиваться вдоль осей с большим диаметром, таким образом соответствующие переменные станут все менее существенными для определения кластера. По другим хе переменным, где диаметр невелик, будут сохраняться существенные ограничения.

В задаче 2 даны двумерные наблюдения, и требуется найти кластеры, в которых переменные связаны линейной зависимостью. Кластеры могут иметь пересечения, и направление каждого из/ них может быть различно. Для тройки x,y,zea определим h(x,y,z) как длину наибольшей высоты в треугольнике с вершинами х, у и z. Полохим:

Я^с,А) = max. h(x,y,z¡ ■ У, ZEA

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

В §3.5 рассматриваются алгоритмы построения обобщенной иерархии кластеров. Основой алгоритма служат свойства ультраметрической л-функции из §1.1, даюиие путь к построению расширяющихся t-кластеров с нарастающим значением с. Поскольку допускаются пере-

сечения, число кластеров в одном уровне может-оказаться весьма велико, что усложняет вычисления и создает трудности для интерпретации. Поэтому предлагается 'прореживание", т.е. исключение кластеров, создающих в одном уровне значительные пересечения, особенно многократные. Для этого используется функционал (8) в варианте, когда~он оценивает близость набора подмножеств к разбиению.

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

Выводы:

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

2. Гарантируется существование с-устойчивых множеств при любом t для мер связи типа элемент-множество (я-функпий), относящихся- к следующим Классам: невозрастающиа," ультраметрические,' суммируемые, порядково однородные, с-устойчивые множества для неубывающих ультраметрических мер суть максимальные, не содержащие квазиядер соответствующих монотошшх систем, которые могут интерпретироваться как разреженные подмножества.

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

4. Поиск диагностического, решения в модели Пенга-Реджиа- сводится к максимизации субмодулярной функции множества.

5. Построен алгоритм поиска максимума субмодулярной функции множества, оптимальный по Шеннону.

6. Неубывающие ультраметрические л-функции приводят к обобщению иерархического кластер-анализа, допускающему пересекающиеся кластеры и/или кластеры, не покрывающие всего классифицируемого множества. Даны необходимые и достаточные условия того, чтобы кластеры не пересекались, и того, чтобы они составляли покрытие.

- IB -

7. Через понятие t-устойчивого множества описываются методы кластерного анализа, основанные на теории .графов: методы-сильной и слабой i-связи, к-перекрытия, k-клики, блихайшегб соседа. ■ клики, прямой и непрямой кластеризации по г-диаметру.

8. Обобщенный иерархический кластер-анализ прилагается к задачам поиска кластеров малой размерности и приближенно линейных кластеров на плоскости.

9. Для умёньшения пересечений кластеров в обобщенном иерархическом анализе рекомендуется механизм "прореживания", основанный на субмодулярном функционале.

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

Список работ, опубликованных по теме диссертации:

1. А. В. Генкин, Ю. М. Закс, И. Б. Мучник, "Структура финальных множеств контрмонотонной системы и алгоритмы ее изучения," в кн: Методы и алгоритмы анализа эмпирических данных, Москва, Институт проблем управления, 1988, с. 35-42.

2. A.B.Генкин, D.M.Закс, И.Б.Мучник, "Сопоставление структур монотонной и контрмонотонной систем," в кн: Методы и алгоритмы анализа эмпирических данных, Москва, Институт проблем управления, 1988, с. 42-48... - •

3. A.B.Генкин, И.Б.Мучник. Оптимальный поиск максимума субмодулярной-функции. Автоматика и телемеханика. ы8, 1990. С. 193-14?.

4. А. В. Генкин, И. Б.,Мучник. Монотонные системы на частично упорядоченных множествах. Тезисы докладов iи Всесоюзной школы-семинара "Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание". Одесса, 1990. С. 35-43.

5. А. В. Генкин, И- Б. Мучник. Иерархии пересекающихся кластеров. Там же. С. 15-18. '

6. A.B.Генкин, И.Б.Мучник, И.А.Рыбина. Оптимизация субмодулярных и модулярных функционалов на иерархически порожденных решетках в применении к задаче автоматической классификации. Там же. С. 68-74.

7. И. Б. Мучник, А. В. Генкин. t-кластеры в задаче распознавания. Теория и практика классификации и систематики в народном хозяйстве. Пущино, 1990. С. 88.

8. A.V.Genkin. l.B.Muchnik. Fixed points approach to clustering. Journal of Classification. Vol.10, No.2. 1993, 219-240

Подписано к печати"

09

.1995 года.

Отпечатано на ротапринте в Формат бумаги 30x42/4 Производственном комбинате Объем ^

пл.

Литературного фонда' ■'. " Зах.

Тир. 100

ул. Усиевича, д, 8-а

Тел. 152-17-71