Введение к работе
^:-j\7ljv^^2l^iLJSi.^^SI^MM» S решении проблемы автоматизации научных исследований важное место занимает задача построения распознающих систем, необходимых для классификации сб-ьектов и их состояний. Использование блоков распознавания и автоматической классификации позволяет псеыскть скорость и качество принимаемых решений, что обеспечивает им широкое применение при создании АСНИ, АСУ, АРМ, при решении задач технической диагностики и контроля технологических процессов, а также при разработке экспортных систем. Необходимость з решении задач, связанных с автоматической классификацией (группировкой объектов), возникает при обработке разнообразных экспериментальных данных в медицине, геологии, биологии, физике, экономике, социологии и других областях науки»
Информация об объектах часто представляется з виде таблицы экспериментальных дг«ш:ых( эмпирической таблицы), строїш которой соответствуют объектам, а столбцы -некоторым измеренным у них характеристикам (признакам), В ходе анализа таких таблиц, проводимого с целью получения определенного рода выводов о закономерностях и структуре изучаемого множества объектов, возникают разнообразные задачи, з частности, задача группировки, заключающаяся в разбиении исходного множества на группы "похожих" в некотором смысле объектов. В литературе такие задачи называются также задачами автоматической классификации, таксономии, самообучения, кластерного анализа (кластеризации). Решение задачи автоматической классификации наряду с некоторыми другими (обучение "с учителем", выбор информативных признаков и т.п.) занимает одно*из центральных мест при построении рассмотренных выше систем распознавания.
Получаемые на практике таблицы часто обладают рядом свойств, которые существенно затрудняют, а порой делают
вовсе невозможным применение известных методов группировки. К числу таких свойств относятся следующие:
наличие как качественных, так и количественных признаков, измеренных в разных шкалах;
высокая априорная неопределенность (отсутствие информации о виде распределений в пространстве признаков, о зависимости пли независимости признаков и т.п.);
использование из-за недостаточного знания структуры объектов большого числа признаков, среди которых могут быть "шумовые" и дублирующие;
наличие "пропусков" (неизмеренных значений ряда признаков у некоторыхобъектов).
Таблицы, характеризующиеся такими свойствами, назовем РП-таблнцами, Методы, позволяющие решать задачу группировки на РП-талнцах, очевидно, подходят и для традиционно используемых таблиц (однотипные, количественные пли булевые, признаки, без "пропусков" и т.д.). В .этом смысле класс РП-таблнц можно трактовать более широко, как класс таблиц, которые могут обладать (ibj но обязательно обладают) сформулированными выше свойствами. Тогда обычлыс таблицы данных представляются частными случаями РП-таблиц. Методы, позволяющие обрабатывать таблицы, облгщающне некоторыми из пере- \ численных выше свойств, стали развиваться относительно подавно. Анализ советской и зарубежной литературы показывает, что в настоящее время отсутствуют методы группировки для таблиц со всеми свойствами РП-класса. С учетом того, что из-за существующей тенденции к усложнению пзучае.\шіх объектов все большее число прикладных таблиц попадает в рассматриваемый класс, актуальность поставленной задачи очевидна.
В работе для решения задачи группировки введен новый класс логических функций. Выбор такого класса функций объясняется следующими причинами:
- логические функции успешно применялись для реше
ния ряда задач анализа данных на РП-таблицах (распозна
вание, дшамическое прогнозирование и др.);
— класс логичоскл;: функций обладает свойством универсальности в том смысле, что позволяет, с одной стороньі, варьировать сложность функції:'; для описания таксолоь, а с другой стороны - формировать описания в разиliх :; ризнаковых пространстзах;
представление результатов группировки в виде логических высказываний дает при разработке экспертных систем возможность формирования базы знаний в процессе анализа данных (в настоящее время формирование баз знаднії осуществляется, как правило, только путем формалн- зацпи заключений экспертов), при этом облегчается совместная обработка знаний, полученных в результате анализа данных и непосредственно от эксперта;
класс логических функций обеспечивает простоту и наглядность в смысле содержательной интерпретации результатов группировки, так как они представляются па языке, близком к естественному языку логических 'суждений.
Следует заметить, что при анализе РП-таблиц форма представления результатов имеет особое значение. На одно из первых мест, наряду с точностью, выдвигается требование простоты их интерпретации для специалистов, прикладных областей. Особенно важно это для задачи группировки, возникающей обычно на начальных этапах исследований и формулирующейся на основе содержатель-* пых представлений о похожести объектов, ибо результаты должны позволять делать первые обобщающие заключения о структуре и закономерностях изучаемых данных.
Цель работы заключалась в разработке hol-.ых методов группировки объектов и соответствующего программного обеспечения, позволяющих решать поставленную задачу в условиях высокой априорной неопределенности данных,разнотипности признаков и наличия "пропусков".
Методы исследования основаны на использовании аппарата дискретной математики, математический логики, статистики, теории измерений п теории графов.
1. Разработан новый подход к решению задач::
группировки, учитывающий специфику РП-табліщ, основан
ный па использовании гласе а логкчестспх функции. В рам
ках этого подхода:
предложена формальпо-л постановка зад-ічи группировки, учитывающая особенности РП~та(5лпц:
дано описание класса логических функции, которые могут применяться для решения задачи группировки;
предложены и исследованы новые критерии качества, на ссноьо которых разработаны даа алгоритма группировки для РП-та блиц.
2. Разработаны новые методы оценивании информа
тивности признаков и обработки пропущенных значений в
процессе решения задачи группировки обтектов при исполь
зовании класса логических функций,
3«, Разработан комбинированный алгоритм длк разнотипного признакового пространства, сочетающий преимущества использования логических функций с достоинствами одного из известных алгоритмов группировки, обеспечивающего ьыделепне сложных структур данных.
4, Проведено теоретическое и экспериментальное исследование разработанных методов и алгоритмов на тсстойых и прикладных задачах.
Практическая ценность и реализация результатов работы. Предложенные ъ диссертационной работе методы группировки имеют явную практическую направленность, поскольку полнее, чем другие методы, учитывают особенности прикладных задач, отраженные в определяющих свойствах РП~таблкд. Основной практически:1, результат заключается и разработке пакета программ ЛОГР, предназначенного для решения различных типов зйцоч группировки з условиях РП-таблкц с параллельным построением
информативных систем признаков и прогнозированием пропущенных значений. Форма представления результатов значительно облегчает специалистам прикладных областей формулировку обобщающих выводов о закономерностях, структуре и причинно-следственных связях исследуемого множества данных, необходимых при решении-задач прогнозирования и управления. Результаты решения прикладных задач подтверждают необходимость формирования таксонов в разных признаковых подпространствах.
Разработанное" программно-алгоритмическое обеспечение внедрено в ряде организаций в г.г. Уфе, Новосибирске, Красноярске, где использовалось при решении задач, связанных с управлением техническими системами и автоматизированной обработкой данных в научно-практических исследованиях, В составе комплексной системы анализа данных применялось при проектировании специализированного оборудования на одном из предприятий г.Уфы для выявления причинно-следственных связей, приводящих к браку продукции (годовой экономический эффект составлял 2,5 тыс. руб.). Программы, входящие в пакет ЛОГР, применялись в ПГО "Енисейгеофизика*' при определении залежей полезных полезных ископаемых по косвенным признакам, в Институте терапии СО АМН СССР при проведении исследований, связанных с выявлением закономерностей протекания инфаркта миокарда и прогнозированием исходов и отдаленных последствий заболевания, в Институте леса и древесины СО АН СССР им. Сукачева -в процессе автоматизированной обработки данных дистанционного зондирования с целью индикации повреждений растительности и решения других лесобиологических задач.
Апробация работы. Основные положения диссертационной работы доложены и обсуждены на Ш Всесоюзной школе-семинаре "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа", Цахкадзор, 1983 г.; Республиканской школе-семинаре
'Логико-комбинаторные методы в распознавании образов и искусственном интеллекте", Кишинев , 1985; V республиканском симпозиуме "Методы и программное обеспечение обработки информации и прикладного статистического анализа данных", Минск, 1985; У1 Всесоюзном совещании-семинаре "Непараметрические и робастные методы статистики в кибернетике и информатике", Томск, 1987; УП Всесоюзной школе-семинаре "Непараметрические и робастные методы статистики в кибернетике", Иркутск, 1990; Всесоюзной с международным участием научно-технической конференции "Применение статистических методов в производстве и управлении", Пермь, 1990; Всесоюзном научно-техническом симпозиуме с международным участием "Теория и практика классификации и систематики в народном хозяйстве", Пушино, 1990; на конференциях молодых ученых и семинарах в ВЦ СО АН СССР в г. Красноярске и в ВЦ СО АН СССР, ИМ СО АН СССР, НЭТИ.
Публикации. По теме диссертации опубликовано 12 работ.
Структура работы. Диссертация состоит из введения, 4 глав, заключения, приложения с 4 документами о внедрении, 6 таблиц, 7 рисунков, списка литературы из 145 наименований. Общий объем диссертации 160 стр. машинописного текста, включая рисунки, таблицы, приложения.
