Введение к работе
Актуальность темы. Существенную роль в анализе данных, описывающих слабоформализованные процессы и системы, игравт задачи, в которых"ответ ищется не в виде чисел или совокупностей чисел (векторов, матриц), а в виде конечных множеств или их наборов. С одной стороны, это;объясняется тем. что сами данные представлены в виде значений переменных, значительная часть которых измерена в конечных нечисловых икалах. С другой стороны, результаты дойны восприниматься и интерпретироваться специалистом предметной области, интегрироваться в базы профессиональных знаний, что требует их представления в логическом виде. Последнее обстоятельство особенно существенно при построении партнерских систем (В. С. Переверзев-Орлов).
Самым естественным примером этого класса являются методы
кластерного анализа. Кластерный анализ применяется для выявления
скрытой структуры данных при недостатке априорной информации. В
случае успеха, когда удается найти существенно различавшиеся мехду
собой кластеры, задача построения модели отдельно для каждого из
них мохет оказаться значительно проще исходной. Результаты клас
терного анализа могут представлять и непосредственный интерес для
содержательной интерпретации. ^
Однако некоторые практические задачи, родственные кластерным, на самом деле не могут быть эффективно решены опираясь на известные представления о кластере. Далее, существует ряд практических задач, имеющих вид поиска поямнохеств, но никак не связанных с представлением о кластерах, при всем разнообразии этих представлений, : встречающихся в литературе. Приведем несколько характерных примеров задач, возникающих при анализе данных главным образом из области клинической медицины, а также из других слабоформализован-ннх областей:
-
Поиск кластеров, описываемых малым числом переменных.
-
Поиск кластеров, приближенно, описываемых линейной зависимостью между переменными.
-
Поиск набора симптомов для порогового синдрома.
-
Поиск набора частных решателей для систем распознавания, основанных на голосовании.
5. Поиск диагностического решения в модели Пенга-Редхиа.
Задачи \ и 2 Обладают рядом свойств, затрудняюяих их решение
: опорой на принятые представления о кластерах: искомые подмно-
- г -
хества могут пересекаться и не обязательно долхны покрывать все рассматриваемое мнохество; отсутствует априорное знание о числе или масштабе кластеров. Для задач 3, 4 и 5 кластерная интерпретация вообще неадекватна. Во всех задачах недостаточно рассмотрения попарных взаимодействий.
v В работе предлагается подход, основанный на явном формулиро
вании искомых свойств подннохеств, причем упор,, делается на свой
ства отдельного подмнохества. Свойства набора подннохеств, в част
ности такие как свойство образовывать разбиение, рассматриваются
как вторичные. Подход основан на мерах связи типа элемент - мно
хество: для кахдого элемента х и подмнохества а конечного мнохест-
ва и мера связи определяется числовой, функцией к(х,а) (для крат
кости - я-функцией). В качестве модели подмнохества, которое лол-
хно послухить результатом анализа данных в задачах типа рассмот
ренных выше и родственных им, вводится понятие t-устойчивого мно-
хества - такого подмнохества а, что:
(la) jrfx,A;
(16) n(x,A)>t, для любого х, не принадлехаиего а
Такой подход позволяет описывать известные методы (в частности, кластерные) и предлагать новые методы, обеспечивающие построение подннохеств с заданными свойствами. Он помогает выявлять структуру данных, избегая опасности навязать-данным структуру, свойственную применяемому методу.
Цель исследования состоит в:
разработке методов анализа данных, обеспечивающих построение подмножеств конечного мнохества с заданными свойствами;
разработке эффективных алгоритмов анализа данных указанного класса.
Научная новизна работы.
1. Введено понятие с-_устоичивого подмнохества, которое предлагается в качестве модели искомого подмнохества для задач анализа данных.. Выделены классы я-функций, для которых t-устойчивые мнохества существуют при любом с, и изучены свойства этих ннохеств: взаимное полохение и изменение в зависимости от параметра t. Установлена связь с ядрами монотонных систем. Основные понятия"теории монотонных систем перенесены на конечные частично-упорядоченные мнохества.
-
Задача построения набора частных решателей для голосования приведена к максимизации субмодулярной функции. Предлохен путь максимизации - метод распределенного доучивания.
-
Построен оптимальный алгоритм поиска максимума субмодулярной функции и вычислена функция Шеннона для этой задачи.
-
Построено обобщение иерархического кластерного анализа, допускающее, кластеры, пересекающиеся на одном уровне, и неполные классификации.
Положения, выносимые на зашиту:
метод построения набора частных решателей для распознавания;
обобщенный иерархический кластер-анализ;
--оптимальный алгоритм поиска максимума субмодулярной функции.
Теоретическая и практическая значимость. В работе показано, . что ряд методов и практических задач анализа представиш в виде поиска t-устойчивых подмножеств конечного множества, в частности -поиска максимума субмодулярной функции.
Предложена модель выбора множества частных решателей, приводящая к максимизации субмодудярной функции множества. При различном выборе параметров модель позволяет строить наборы решателей для схем распознавания, основанных на голосовании, или для концептуального кластер-анализа. 'Предложен эвристический алгоритм" максимизации, работающий параллельно с поиском решателей, и интерпретируемый как распределенный вариант классического доучивания.
Построено обобщение иерархического кластер-анализа, допускающее пересекающиеся кластеры и неполные классификации, и открывающее путь к построению естественных кластеров с заданными свойствами. Метод прилагается к задачам поиска кластеров малой размерности и приближенно линейных кластеров на плоскости.
Для уменьшения пересечений кластеров в обобщенном иерархическом апализе предложен механизм "прореживания", основанный ва суб-модулярном функционале. Метод распространен на произвольные неубывающие я-функции.
Построен оптимальный алгоритм поиска максимума субнодулярной функции и другие алгоритмы поиска t-устойчивых множеств.
\
Апробация работы. Отдельные результаты работы докладывались
на .1 и Всесоюзной иколе-семинаре. "Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание"
(Одесса, 1990г), Всесоюзном научно-техническом симпозиуме с международным участием-"Теория и практика классификации и систематики в народном хозяйстве" (Пущино, 1990г.), семинаре "Сложность алгоритмов" МИАН и ВЦ АН СССР (1991г.), семинаре "Дискретная оптимизация" ИПНТП АН СССР (1991г.).
Публикации. По теме диссертации опублико'вано 8 работ.
Структура работы. Работа состоит из введения, 3 глав и заключения. Список литературы включает 61 наименование.
