ВВЕДЕНИЕ
Существуют различные технологии принятия решений: построение
математических моделей, использование голосования, учет экспертных оценок, таксономия, и т.д.
Наиболее мощной методикой сегодня является принятие решений на базе оптимизационных математических моделей. Достоинством ее является гарантированность получения оптимального решения, а к недостаткам можно отнести её ресурсоёмкость, сложность реализации и требование высокой квалификации лиц, использующих эту технологию. Так, для построения математической модели требуется высокая компетентность исследователя, хорошее знание предметной области разрабатываемой модели, высокая математическая культура разработчиков, навыки работы на ЭВМ и т.д. Тем не менее, несмотря на перечисленные трудности, данный способ является наиболее предпочтительным во многих ситуациях.
Полярной по отношению к этой технологии принятия решений, является другая, более древняя и более простая — таксономия — теория классификации и систематизации сложно организованных областей действительности [1]. Суть таксономии в свое время изложил Демокрит в «Письме ученому соседу»: «Если тебе, мой друг, нужно разобраться в сложном нагромождении фактов или вещей, ты сначала разложи их на небольшое число куч по похожести. Картина прояснится, и ты поймешь природу этих вещей»[2]. Иными словами принятие решения с помощью таксономии сводится к классификации: достаточно отнести объект к одному из таксонов, для компонент которого известно решение. Таким образом, достоинством таксономии является простота, этим объясняется её популярность: на ней базируются различные уставы (например, воинские, монастырские, учебных заведений), кодексы, методы диагностики в медицине и технике и т.п. Особо важное место таксономия занимает в тех отраслях науки, которые связаны с изучением массовых явлений и процессов. Необходимость развития методов таксономии и их использования
продиктована, прежде всего, тем, что они помогают построить научно обоснованные классификации, выявить внутренние связи между единицами наблюдаемой совокупности. Кроме того, методы таксономии могут использоваться с целью сжатия информации, что является важным фактором в условиях постоянного увеличения и усложнения потоков статистических данных [3-9].
Первые публикации по таксономии (кластерному анализу) появились в конце 30-х годов нашего столетия, но активное развитие этих методов и их широкое использование началось в конце 60-х — начале 70-х годов. В дальнейшем это направление многомерного анализа очень интенсивно развивалось. Появились новые методы, новые модификации уже известных алгоритмов, существенно расширилась область применения таксономии. Если первоначально методы многомерной классификации использовались в психологии, археологии, биологии, то сейчас они стали активно применяться в социологии, экономике, статистике, в исторических исследованиях. Особенно расширилось их использование в связи с появлением и развитием ЭВМ и, в частности, персональных компьютеров. Это связано, прежде всего, с трудоемкостью обработки больших массивов информации (вычисление и обращение матриц больших размерностей).
Обычно о необходимости построения таксономии говорят в тех случаях, когда возникает необходимость в систематизации некоторой предметной области, которая оказывается слишком сложной для того, чтобы провести ее систематизацию на основе некоторой достаточно просто выводимой классификации объектов, ее составляющих.
В последнее время потребность в таксономии в самых разных областях проявляется все чаще, прежде всего, в связи с процессами использования новых информационных технологий (НИТ) для обработки информации. В настоящее время практически невозможно найти области научных исследований и практической деятельности, в которых не разрабатывались
6
бы базы данных (БД) или базы знаний (БЗ). В свою очередь создаваемые БД/БЗ должны удовлетворять определенным требованиям их использования для решения практических задач пользователями систем и/или служить одной из составляющих более сложных систем обработки информации -инструментальных аналитических систем, систем автоматизированного проектирования, систем поддержки принятия решений. И зачастую оказывается, что только предварительные исследования по таксономии соответствующих предметных областей позволяют находить достаточно эффективные и гармоничные решения по систематизации и классификации этих областей, что, в свою очередь, дает возможность разрабатывать эффективные БД с широким диапазоном их возможного использования.
В области создания информационных технологий и автоматизированных информационных систем (ИТ и АИС) необходимость в развитии таксономии осознана достаточно давно. Первые шаги в этом направлении были связаны с систематизацией огромного количества стандартов, регламентирующих развитие вычислительных систем и сетей [10-14].
К недостаткам классической таксономии можно отнести неоднозначность получаемых решений, т.е. возможность получения различных вариантов разбиений, что в значительной мере обесценивает полученное решение.
Таким образом, целью настоящей работы является совмещение сильных сторон математического моделирования и таксономии, то есть дальнейшее развитие оптимизационных подходов применительно к задачам таксономии, включающее создание системы оптимизационных математических моделей, описывающих задачи таксономии, и разработку, а также привлечение существующих оптимизационных процедур для поиска решения на построенных моделях.
7
Основной идеей работы является разработка математического аппарата и создание на его основе программных средств поиска оптимальных решений для ряда прикладных задач таксономии.
Научная новизна диссертационной работы заключается в:
• дальнейшем развитии теоретических подходов оптимальной таксономии, включающих построение математических моделей задач таксономии применительно к различным критериям разбиения и предметным областям, а также выделение алгоритмов поиска оптимальных группировок на построенных математических моделях;
• выделение случаев, допускающих применение простых и эффективных процедур поиска оптимальной группировок в задачах таксономии.
• разработке методики выбора оптимизационной математической модели применительно к конкретным задачам таксономии.
• адаптации развитых теоретических подходов применительно к прикладным задачам из разных предметных областей. В частности разработаны: математическая модель поиска оптимальных режимов изготовления микроканальных пластин; методика оценки показателей толерантности и напряженности в регионах; технология прогнозирования персональной успеваемости студентов в вузе. Практическая значимость работы заключается в разработке пакетов
программ, предназначенных для автоматизации поиска оптимальной таксономии применительно к различным предметным областям. В данной работе на защиту выносятся:
• содержательные и формальные постановки оптимизационных задач таксономии объектов применительно к различным предметным областям;
• алгоритмы поиска решений оптимизационных задач таксономии на построенных математических моделях;
• программные средства поддержки поиска решений оптимизационных задач таксономии применительно к различным предметным областям;
8
• результаты экспериментального анализа эффективности созданных
программных средств.
Апробация результатов работы.
Основные положения диссертации докладывались на Межвузовской научно-практической конференции в г. Владикавказ 2001 - «Новые информационные технологии и их применение»; Международной конференции Владикавказ 2002 - «Новые информационные технологии в науке, образовании, экономике»; Международной конференции в г. Владикавказе, 2002 — «Информационные технологии и системы: наука и практика»; Международной научно-технической конференции, Владикавказ, 2003 - «Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике», на ежегодных научно-практических конференциях Северо-Кавказского горно-металлургического института (государственного технологического университета) и на семинарах кафедры автоматизированной обработки информации СКГМИ. По материалам диссертации опубликовано 7 печатных работ.
Разработанные методы построения оптимальных группировок данных внедрены в различных отраслях народного хозяйства, образовании и медицине.
Структура и объем диссертации. Диссертация состоит из введения,
четырех глав, заключения, списка литературы из 121 наименования, приложения, содержит 31 рисунок, 6 таблиц и 144 страницы текста.
9 ГЛАВА 1 ОБЗОР МЕТОДОВ ТАКСОНОМИИ.
Целями первой главы диссертации являются:
• описание основных методик и приемов автоматической классификации
• обзор содержательных и формальных постановок задач, решаемых таксономией в настоящее время;
• анализ используемых при решении задач таксономии алгоритмов;
• определение степени привлечения оптимизационных подходов к решению задач таксономии
• исторический обзор развития таксономии и кластерного анализа в России и за рубежом
Современные требования к качеству классификации объектов предполагают учет при решении этих задач всех значащих факторов. Так, например, классификация предприятий определенной отрасли в соответствии с условиями их хозяйственной деятельности требует учета технико-экономических факторов (масштаб производства, фондовооруженность, энерговооруженность и т.д.), социальных факторов (квалификация рабочих, текучесть кадров и т.д.), факторов природной и технологической среды (климатические условия, условия сбыта и транспортировки сырья, продукции и т.п.). При этом каждый из факторов может в свою очередь характеризоваться еще несколькими показателями (например, масштаб производства — размером основных фондов, численностью работников и т.д.), что приводит к большому числу признаков, описывающих деятельность предприятия, причем не всегда с достаточной определенностью можно отнести тот или иной фактор к разряду объективных. Все это приводит к тому, что экспертные типологические группировки одних и тех же предприятий, построенные по небольшому числу показателей, зачастую
10
оказываются различными. Различия в классификациях, очевидно, отображаются и в дальнейших теоретических построениях или практических рекомендациях. Таким образом, весьма актуальна разработка методов классификации, учитывающих большой набор признаков и зависимостей между ними. Наиболее действенный количественный инструмент исследования классификации подобных объектов, явлений, описываемых большим числом характеристик, являются методы кластерный анализ, таксономия.,
Таксономия в последнее время существенно расширила диапазон своего применения, интенсивно вторгаясь в ранее недоступные области. К последним можно отнести распознавание образов по эталонам, выбор эффективных режимов технологических процессов, прогнозирование персональной успеваемости учеников и студентов, поиск месторождений полезных ископаемых и ряд других. Группировка объектов (часто употребляют также термины «автоматическая классификация», «самообучение», «кластеризация» и т.д.) по похожести их свойств упрощает решение многих практических задач анализа данных.
Алгоритмы таксономии нашли широкое применение при решении разнообразных прикладных задач.
1.1 Основные понятия. Базовые эмпирические гипотезы.
Кластерный анализ — это совокупность методов, позволяющих классифицировать многомерные наблюдения, каждое из которых описывается набором исходных переменных Х\, Х2, ..., Хт. Целью кластерного анализа является образование групп схожих между собой объектов, которые принято называть кластерами (классами, таксонами, сгущениями).
В отличие от комбинационных группировок кластерный анализ приводит к разбиению на группы с учетом всех группировочных признаков
11
одновременно - политетический подход. При этом, как правило, не указаны четкие границы каждой группы, а также неизвестно заранее, сколько же групп целесообразно выделить в исследуемой совокупности.
Кластерный анализ предназначен для разбиения множества объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации.
Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования [15]:
1. Внутри групп объекты должны быть тесно связаны между собой.
2. Объекты разных групп должны быть далеки друг от друга.
3. При прочих равных условиях распределения объектов по группам должны быть равномерными.
Требования пунктов 1 и 2 выражают стандартную концепцию компактности классов разбиения [16]; требования пункта 3 состоит в том, чтобы критерий не навязывал объединения отдельных групп объектов.
Кластерный анализ в отличие от большинства математико-статистических методов не накладывает никаких ограничений на вид рассматриваемых объектов, и позволяет рассматривать множество исходных данных практически произвольной природы.
Строгие математические методы, используемые в математической статистике, разработаны для случаев, когда о распределениях анализируемых генеральных совокупностей известно все, что только может потребоваться в процессе решения задачи: известны виды законов распределений и все их параметры, априорные вероятности появления образов, матрица потерь от ошибок и т.д.
К сожалению, при решении реальных задач анализа данных такие условия не встречаются. Для приведения задачи к виду, при котором можно было бы применить тот или иной статистический алгоритм, нужно к имеющейся объективной информации добавить ряд субъективно
12
выбираемых предположений или гипотез. Этот этап привнесения эвристических гипотез имеет место во всех случаях решения реальных задач распознавания образов. Дополнительные гипотезы могут носить общий характер или касаться мелких частностей [17].
Гипотеза компактности (Н) состоит в том, что реализации одного и того же хорошо организованного образа обычно отражаются в признаковом пространстве в геометрически близкие точки, образуя «компактные» сгустки. При всей кажущейся тривиальности и легкости опровержения указанная гипотеза лежит в основании большинства алгоритмов не только распознавания, но и многих других задач анализа данных.
Конечно, она подтверждается не всегда. Если, например, среди признаков имеется много случайных, не информативных, то такой случай соответствует плохой организации образов, и точки одного и того же образа могут оказаться далекими друг от друга. Но дополнительно предполагается, что работа по организации образов уже проведена и в многомерном признаковом пространстве найдено такое («информативное») подпространство, в котором точки одного класса действительно образуют явно выделяемые компактные сгустки [16].
Назовем п признаков, входящих в информативное подмножество X, «описывающими»у а номинальный («+1)-й признак z, указывающий имя образа, «целевым».
Пусть А — множество объектов обучающей выборки; q - новый
гх
распознаваемый объект; ^ а — компактность объектов множества А в пространстве п характеристик X. Мера «компактности» может быть любой: она может характеризоваться средним расстоянием от центра тяжести до всех точек образа; средней длиной ребра полного графа или ребра КНП, соединяющего точки одного образа; максимальным расстоянием между двумя точками образа и т.д. Фактически гипотеза Н равнозначна предположению о наличии закономерной связи между признаками X и z, и ее
13
тестовый алгоритм может быть представлен следующим выражением: if [cxA--8cClq) then С;,,
Т.е., если объекты множества А компактны в совместном пространстве (X, z) и объекты множества (A, q) компактны в пространстве описывающих свойств X, то объекты Аид будут компактными и в пространстве целевого признака z. Часто эту гипотезу формулируют так: «Объекты, похожие по п описывающим свойствам X, похожи и по (п + 1)-му целевому свойству z».
Сформулированное выше условие компактности для решения задачи распознавания образов является необходимым, но недостаточным. Мало того, чтобы точки образа А были близкими друг к другу, нужно также, чтобы точки образа В не оказались к ним такими же близкими, т.е. нужно, чтобы сгустки точек разных образов не налагались друг на друга, что будем обозначать так: С-. С учетом этого, гипотезу компактности Н для распознавания образов можно записать в следующем виде: if {C-lB&C^&Cl) then Ci,
Различаются разные варианты гипотезы компактности: гипотеза унимодальной (Ни\ полимодальной (Нр) и локальной компактности {Hl). Проекции компактных сгустков на координатные оси будут также компактными, так что можно различать еще три варианта гипотезы компактности: гипотезу унимодальной проективной (Hup), полимодальной проективной (Нрр) и локальной проективной компактности (Hip).
Гипотеза унимодальной компактности лежит в основе многочисленных алгоритмов таксономии, с помощью которых получаются таксоны простой геометрической формы - в виде гиперсфер или гиперпараллелепипедов. Например, алгоритмы семейства FOREL формируют сферические таксоны заданного радиуса R [18].
Если в системе содержатся неинформативные признаки, то они «размывают» компактность и затрудняют принятие правильных решений.
14
Задача выбора информативных признаков состоит в поиске подпространства, в котором характеристика компактности достигает максимального значения.
При использовании гипотезы локальной компактности критерием информативности подсистемы признаков может служить количество опорных точек (прецедентов), необходимых для безошибочного распознавания обучающей последовательности.
Реальные таблицы могут содержать пробелы: значение некоторых характеристик у некоторых объектов в таблице не указаны. Для предсказания значений пропущенных элементов используется гипотеза полимодальной компактности.
Гипотеза Х-компактности (ХН). (Н) оперирует значениями евклидовых расстояний между векторами в пространстве описывающих характеристик. Однако на некоторых примерах можно показать, что важную роль в задачах анализа данных играют не столько сами расстояния, сколько отношения между ними. Глаз человека улавливает нарушение однородности расстояний между соседними точками и придает этому факту большее значение, чем абсолютной величине расстояний. Результаты естественной для человека таксономии часто не могут быть получены или объяснены с позиций гипотезы компактности. Таким является, например, случай, представленный на рис. 1.1. Гипотеза Х-компактности позволяет легко получать и просто объяснять подобные результаты.
?mln
Рис. 1.1 Примеры множеств, таксономия которых с помощью гипотезы
компактности затруднительна
15
Формулировка гипотезы ^.-компактности опирается на понятие X-расстояния. Если определить расстояния между всеми парами точек множества А, то можно построить полный граф, который соединяет все т точек друг с другом. Если на этом графе выделить две вершины а и ?, обозначить длину связывающего их ребра через а, а длину минимального из смежных ему ребер через ?m,„, то отношение длин этих ребер Х=а I ?mjn будет характеризовать меру локальной неоднородности расстояний или X-расстояние между точками аи ?. Пользуясь этим методом, вычисляется X-расстояния между всеми парами из т точек, и строится граф без петель, который соединяет между собой все точки ребрами, суммарная А,-длина которых минимальна. Такой граф называется кратчайшим незамкнутым путем (КНП) [19]. Теперь ^-расстоянием между двумя любыми точками будем считать сумму А,-длин тех ребер, по которым проходит путь между ними по КНП. Локальная «неодинаковость» плотности точек, соседство «неоднородных» по длине участков КНП легко улавливается зрением и однозначно связывается с величиной ^-характеристики.
Исходя из этого, по аналогии с гипотезой компактности гипотезу X-компактности (ХН) можно сформулировать следующим образом: реализации одного и того же хорошо организованного образа отражаются в признаковом пространстве в А,-близкие точки, образуя «Х-компактные» сгустки.
По аналогии с гипотезой компактности можно различать гипотезы унимодальной (АНи), полимодальной (АНр) и локальной (ХШ) X-компактности, а также все их проективные версии: (АНир), (АНрр) и (AHlp).
На базе этой более сильной гипотезы можно построить новые алгоритмы анализа данных. Примером может служить алгоритм таксономии X-KRAB.
16
1.2 Меры близости и сходства
Выбор метрики является узловым моментом в таксономии (кластерном анализе), от него решающим образом зависит окончательный вариант разбиения объектов на группы при заданном алгоритме разбиения [20]. В каждой конкретной задаче этот выбор производится по-своему, с учетом главных целей исследования, физической и статистической природы исследуемой информации и т.п.
Любая мера близости представляет собой некоторую функцию, ставящую в соответствие каждой паре точек (Xit Xj) некоторое число d(Xh XJ), характеризующее степень «близости» между объектами Xt и Xj. Определение 1.1
Неотрицательная вещественнозначная функция d(Xh XJ) называется функцией расстояния (метрикой), если:
а) d[xt,Xj)>0 для всехXt иXj из Ер;
б) d(x„Xj)= 0 тогда и только тогда, когдаX,=Xj\ B)d(xi,XJ)=d(xJ,Xi);
г) d(xi,XJ)?„[21,22,23].
Рассмотрим некоторые, наиболее употребительные показатели расстояния.
( w
Xt, X
Пространство признаков в данном случае представляет собой т-мерный двоичный куб, расстояние между вершинами которого равно числу несовпадающих разрядов соответствующих дя-разрядных двоичных векторов - описаний объектов щ и и,.
\ Гт i mV2
Евклидово расстояние — d2 \Xi, X}) = ^ \Xlk) - X(k))
17
Это наиболее распространенная мера сходства. Недостаток ее — не учитывается возможная неравноправность осей пространства. При ненормированных осях для количественных (небулевых) признаков возможен случай, когда объекты, сходные по всем признакам, кроме одного, по которому они сильно разнятся, будут находиться далеко друг от друга в евклидовом пространстве. Если признаки бинарные, то евклидова и хеммингова метрики совпадают.
Отмеченный выше недостаток в ряде случаев можно устранить подбором весов са^к\ и тогда мерой сходства будет служить взвешенное
евклидово расстояние: d\ (xt, Xj) = | ? a>(k) • (х™ -1|"П '; ]Г ф(1с) = 1
Координаты объектов Х\к) в этом случае (как и в остальных,
приведенных ниже) - это значение признаков, как правило, центрированное относительно среднего значения по совокупности и отнесенные к дисперсии. Выбор весов признаков так же, как и состав набора признаков, объем и структура выборки, находятся в руках исследователя, что порождает большую вариантность расчетов. Вообще говоря, выбор весов признаков связан с проблемой нахождения информативной системы признаков. Однако это не означает, что численные методы таксономической классификации нельзя применять, если неизвестны соотношения между признаками, их относительная «важность». Опыт новосибирских специалистов из группы Н.Г. Загоруйко свидетельствует об эффективном применении методов распознавания образов в различных областях науки с использованием нормализации исходных данных, выравнивающих диапазоны изменения всех переменных, т.е. при единичных весах. По мнению новосибирских исследователей, это следствие того, что свойства «особенного» могут проявиться либо при достаточно резком изменении немногих признаков, либо при значительном суммарном изменении многих характеристик. |
