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

П : ■ ,

Ч /.-.' '

МИНИСТЕРСТЕО НАУКИ,

Л"1

! ВЫСШЕЙ ШКОЛЫ И ТЕХНИЧЕСКОЙ ПОЛИТИКИ РОССИИ НОВОСИБИРСКИЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

ПЕСТУНОВА Тамара Михайловна

МЕТОДЫ И АЛГОРИТМЫ ГРУППИРОВКИ ОБЪЕКТОВ В ПРОСТРАНСТВЕ РАЗНОТИПНЫХ ПРИЗНАКОВ, ОСНОВАННЫЕ НА ЛОГИЧЕСКИХ ФУНКЦИЯХ

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФ ЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск 1992

Работа выполнена в Вычислительном центре СО РАН в г. Красноярске

Научный руководитель - доктор технических наук,

профессор Г.С.Лбов!

Официальные оппоненты - доктор технических наук,

профессор В.И.Котюков, кандидат технических наук ведущий научный сотрудник В.Г. Лебедев

Ведущая организация - Вычислительный центр СО РАН

(г. Новосибирск)

Защита состоится Ж Л^^/ии-сЛт- 19 года

в /у^' час на заседаний специализированного Совета Д. 063.34,03 в Новосибирском электротехническом институте по адресу: 630092, г. Новосибирск, 92,

пр. К. Маркса, 20.

С диссертацией можно ознакомиться в библиотеке Новосибирского электротехнического института (г. Новосибирск, пр. К. Маркса, 20, НЭТИ).

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

Ученый секретарь специализированного Совета,

к.т.н. „л

Б.Ю.Лемешко

$ _ . ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

.л-Ак^у'альность проблемы» В решении проблемы автоматизация научных исследований важное место занимает задача построения распознающих систем, необходимых для классификации объектов и их состояний. Использование блоков распознавания и автоматической классификации позволяет псеысить скорость и качество принимаемых решений, что обеспечивает им широкое применение при создании АСНИ, АСУ, АРМ, при решении задач технической диагностики и контроля технологических процессов, а также при разработке экспертных систем. Необходимость з решении задач, связанных с автоматической классификацией (группировкой объектов), возникает при обработке разнообразных экспериментальных данных в медицине, геологии, биологии, физике, экономике, социологии и других областях науки»

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

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

вовсе невозможным применение известных методов группировки. К числу таких свойств относятся следующие:

- наличие как качественных, так и количественных признаков, измеренных в разных шкалах;

- высокая априорная неопределенность (отсутствие информации о виде распределений в пространстве признаков, о зависимости или независимости признаков и т.п.);

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

- наличие "пропусков" (неизмеренных значений ряда признаков у некоторыхобъектов).

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

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

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

• — класс логически;: функции обяаапг-т свойством универсальности в том сглысле, что позволяет, с одной стороны, варьировать сложность фу и кии:*; для описания тсксолоь, а с другой стороны - формировать описпнип в рази и х ризнакор.ы х лространстзах;

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

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

Следует заметить, что при анализе РП-таблиц форма представления результатов имеет особое значение. На одно из первых мест, наряду с точностью, выдвигается требование простоты их интерпретации для специалистов, прикладных областей. Особенно важно это для задачи группировки, возникающей обычно на начальных этапах исследований и формулирующейся на основе содержатель-* пых представлений о похожести объектов, ибо результаты должнь1 позволять делать первые обобщающие 3с1ключення о структуре и закономерностях изучаемых данных.

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

Методы исследования основаны на использовании аппарата дискретной математики, математический логики, статистики, теории измерений и теории графов.

ик•'я .!■'.а

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

- предлохена формальпа-л постановка задачи группировки, учитывающая особенности РП~та6лпд:

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

- предложены и исследованы новые критерии качества, ¡•:а основе которых разработаны даа алгоритма группировки для РП-та блиц.

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

3«, Разработан комбинированный алгоритм дли разнотипного признакового пространства, сочетающий преимущества использовании: логических функций с достоинствами одного из известных алгоритмов группировки, сбеспочпваю-и;его выделение сло:«дых структур данных.

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

Практическая чинность и. реализация результатов работы. Предложенные ъ диссертационной работе методы группировки имеют явную практическую направленность, поскольку полнее, чем другие методы, учитывают особенности прикладных задач, отраженные в определяющих свойствах РП~таблид. Основной практически:1, результат заключается и раоработке пакета программ ЛОГР, предназначенного для решения различных типов задач группировки в условиях РП-таблид с параллельным построением

б

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

Разработанное" программно-алгоритмическое обеспечение внедрено в ряде организаций в г.г. Уфе, Новосибирске, Красноярске, где использовалось при решении за дач, связанных с управлением техническими системами и автоматизированной обработкой данных в научно-практических исследованиях, В составе комплексной системы анализа данных применялось при проектировании специализированного оборудования на одном из предприятий г.Уфы для выявления причинно-следственных связей, приводящих к браку продукции (годовой экономический эффект составлял 2,5 тыс. руб.). Программы, входящие в пакет ЛОГР, применялись в ПГО "Енисейгеофизика" при определении залежей полезных полезных ископаемых по косвенным признакам, в Институте терапии СО АМН СССР при проведении исследований, связанных с выявлением закономерностей протекания инфаркта миокарда и прогнозированием исходов и отдаленных последствий заболевания, в Институте леса и древесины СО АН СССР им. Сукачева -в процессе автоматизированной обработки данных дистанционного зондирования с целью индикации повреждений растительности и решения других лесобиологических задач.

Апробация работы. Основные положения диссертационной работы доложены и обсуждены на Ш Всесоюзной школе-семинаре "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа", Цахкадзор, 1983 г.; Республиканской школе-семинаре

'Логико-комбинаторные методы в распознавании образов и искусственном интеллекте", Кишинев , 1985; V республиканском симпозиуме "Методы и программное обеспечение обработки информации и прикладного статистического анализа данных", Минск, 1985; У1 Всесоюзном совещании-семинаре "Непараметрические и робастные методы статистики в кибернетике и информатике", Томск, 1987; УП Всесоюзной школе-семинаре "Непараметрические и робастные методы статистики в кибернетике", Иркутск, 1990; Всесоюзной с международным участием научно-технической конференции "Применение статистических методов в производстве и управлении", Пермь, 1990; Всесоюзном научно-техническом симпозиуме с международным участием "Теория и практика классификации и систематики в народном хозяйстве", Пушино, 1990; на конференциях молодых ученых и семинарах в ВЦ СО АН СССР в г. Красноярске и в ВЦ СО АН СССР, ИМ СО АН СССР, НЭТИ.

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

Структура работы. Диссертация состоит из введения, 4 глав, заключения, приложения с 4 документами о внедрении, 6 таблиц, 7 рисунков, списка литературы из 145 наименований. Общий объем диссертации 160 стр. маши-нопирного текста, включая рисунки, таблицы, приложения.

СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность проблемы, рассматриваемой в диссертационной работе, определены предмет и цели исследований, дана общая характеристика работы и описание ее структуры.

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

На основе анализа различий в содержательном понимании задачи, приводящем к еще большему разнообразию на

а

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

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

2..Разнообразные способы введения мер близости и метрик при анализе РП-таблиц не всегда оправданы методологически, а при наличии "пропусков* в принципе Не могут быть использованы,

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

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

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

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

1. Постановка задачи не может быть основана на матрице близости, ибо введение таких мер для РП-таблиц, как указывалось выше, весьма проблематично.

2.(Основными целями исследований, для которых проводится группировка на РП-таЙлицах, являются вышле-ние закономерностей, которым подчиняются структуры изучаемого множества; формирование более компактного описания данных таблицы; использование результатов группировки для последующей классификации новых объектов и прогнозирования., Эти цели диктуют необходимость построения не только групп объектов, но и обобщенных их характеристик в признаковом пространстве.

3. Характеристики групп целесообразно формировать в виде описаний в некотором классе функций, поскольку числовые параметры (такие, как среднее, центр тяжести, разброс и т.п.) оказываются неинтерпретируемыми в разнотипном признаковом пространстве.

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

С учетом этих особенностей задачу группировки целесообразно формулировать в следующем виде.

Пусть эмпирическая таблица "V = {хг } —-— •>

ri=l,N

где х^. - результат измерения некоторого призна-

ка Xj е Х= {Х2|Х2...,ХП} у объекта a¿ изучаемого

множества А = { a-^,a2,."»aN }. Строки таблшы xj =

/12 п ч _ _ г

=\х j ) назовем реализациями; с = \ х^,

Х2 »••• XN } • основе эмпирической таблицы определяется некоторым образом признаковое пространство D = D(u")Каждой реализации, а, следовательно, и каждому объекту соответствует точка признакового пространства. Некоторым точкам признакового пространства могут соответствовать две и более реализаций.

Рассматриваются множества всевозможных разбиений

N к

R^ на множестве реализаций Т , U R-^ ,

к к=1 где - множество разбиений на к групп

С к ¿ N). Каждому r~ £ может быть поставлен

в соответствие набор множеств СО ^ = {т^, Т

в признаковом пространстве D, удовлетворяющий условиям:

VT: € ¿3T; eco , Т.ч. Т. £ Т.;

1 i i 11

Ti n Tj = 0 Vi 4= j, i,j .

Множество таких наборов обозначим £2 ; назовем таксонам и. Для аналитического представления таксонов используется некоторый класс функций Ф. Формализованные таким образом таксоны можно рассматривать, как описания групп из r!jí в D , а также

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

^г* , (О (г*<£ )) = агйтах (аг^тт) Р со) (г^ , 00 (г-^)) в И * Л .

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

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

п --

0 = П В. , где j=l1n определяется множест^-

3 = 1 ^ J ,

вом возможных значений признака X} в эмпирической

таблице ту , вид его зависит рт типа признака.

Пусть ^ = У2>«мУ1чу } ~ множество

несовпадающих значений признака Xj на 'У , ^ КГ, упорядоченное по возрастанию в случае количественного или порядкового признака.

если Xj измерен в шкале наименований или порядка.

= [у^, у^^ для количественного признака Xj.

На О; выделяются подмножества сЬ специального вида (назовем их элементарными подмножествам»}, зависящего от типа признака:

- для количественного Xj с^=[у,у'], у,у* €.

- для порядкового Xj а=(у/у е. Djf У*р< У ^ Уц } при условиии 1 ^ р £ q <

- для признаков в шкале наименований с^ =» {Ур^» Ур2.....У^} , 1 < Р1 < Р2 < .»<РЧ < N3, 1 < ч <

Определение 1. Элементарной логической функцией назовем двуместный предикат I ( ), где х € Э,

с!^ - элементарное подмножество на Х| :

1(х,с1^ |1. если х.(х) €

I О, в противном случае.

в

С использованием элементарных логических функций строятся основные функции для описания таксонов-конъюнкций..

Определение 2. Пусть в X зафиксировано некоторое X' С х, Х'-{Х ,Х.2.....Х]м}, М=/Х*/ < п,

1 ^ .¡1 < )2 < ••• <Зм ^ п»

которому соответствует признаковое подпространство О1.

Тогда конъюнкцию Б определим по формуле Б ( х.сГ ) =

М . . М \ ' /

= & Дх,с1! ) , где с!'= П л с1; Л\ - длина

ш=1 т т=1 Jm

конъюнкции; с!1 - множество истинности. Э- является

таксоном для группы реализаций Г , т.ч. V хет 3(зс;с1,)«1.

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

и распространить на пространство О. Получаемая после такого преобразования конъюнкция эквивалентна Б н имеет вид:

м

5-(х,с1-)= £ х (х,а;гп) = (& 1(х,с1зт))

п

т=1

т=1

&( & Х(х,Б. )) = 3(х,с1>) & 3(х,в" ), т=М+1

//

где: О - подпространство, определяемое подмножеством признаков X" =ХЧ-Х| . Таким образом, при необходимости для удобства рассмотрения конъюнкции можно считать формально имеющими длину п .

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

Определение 3. Пусть имеются конъюнкции 3^(х,с1 ), 32(х,с12 ) ), определенные на подмножествах

признаков Х-*-,

1 ! 1

Пусть Х'= и X , с1'= и «I1 . Дизъюнкцией

/ / \ 1=1 1=1

^(х,«!') назовем функцию, определяемую по формуле:

¿(х,с1') =; V - Э (х.с!1).

Предполагая, что таксоны не должны быть "разорваны" в пространстве, вводится понятие связности дизъюнкции в разнотипном признаковом пространстве.

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

Произвольной конъюнкции 3(х.Тс )= ^ Т( х с1; 1

4 **' т=1 •'т могут быть сопоставлены две величины: Р( б) - вероятность истинности Э при условии равномерного распределения в пространстве признаков, ^ ( э) - частота истинности Э на конкретной эмпирической таблице чт . Качество таксона Т5 , определяемого конъюнкцией Э , оценивается с помощью функции I ( Э ) »^(Э) - Р(Э), характеризующей превышение частоты истинности над априорной вероятностью, предпочтение отдается таксонам с большим ^Э) . Качество взаимного расположения вычисляется с использованием функции А (3-^32 ) =

= (p(s1) + P(S2))/ p(s12),

12'

где S-^2 назовем объединяющей конъюнкцией для S-^ и S2 11 определим ее из условий:

Т^ U Т^ С где "^12 таксон» соответс-h-

вующий sl2i f(S12)=max среди всех S,

удовлетворяющих первому условию.

Функция A(Si,S2) определяет степень ухудшения качества описания точек таксонов Т^ и Т2 при объединении их в один таксон, поэтому меньшее значение A(S-l,S2) должно отвечать лучшему расположению таксонов.

Сформулирован и доказан ряд свойств введенных критериев качества.

Свойство 1 (определяет конструктивный путь построения объединяющей конъюнкции

Пусть имеются конъюнкции S]_(xfT^) и S2(x,T0), определенные ни подмножествах признаков X' и X" соответственно. Тогда S-^2 определена на Х=Х'Л X" а соответствующий ей таксон Т^2=

м12

= П d12 , где Mi 2 =/Х" П X"/,

ш=1 Jm

1 ? 1 2 d . = d. U d; , если Xi_ - портальный jm jm Jm Jm

признак; d"n{z/z eDjm,2min< z < zmax } ,где

zmin=min z zmax= max z ,

. Д ,2 ' z t d. и d- zed. (J dm

jm jm jm jm

если Xjm измерен в шкале не. .слабее порядка.

Свойство 2. Для разбиений на фиксированное число групп максимизация суммарного качества таксонов эквива-

лентна минимизации суммарной априорной (при равномерном распределении) вероятности истинности конъюнкции (для пространства количественных признаков содержательный смысл состоит в минимизации суммарного объема

таксонов Л:

к к Р = 22 г —- Р(Б.)—^шт.

Свойство 3. . Пусть на множестве признаков X1 сформулированы конъюнкции £31 (х,']?1 З^х.Т^), определяющие таксоны Т1 и Т2 и группы реализаций Х± е Тг , Предположим, имеется признак £ X1 и

эдементарные подмножества на нем с!"^ и с!^ такие, что 3^=31&(х,с1£ )и 3'2&(1(х, с!|)) истинны для всех реализаций таксонов Т^ и Т2 соответственно. Тогда . Д ( Б1,32 ) 2. Д ( 31, Б12 )Конъюнкции Б1 ^ и Э'2 можно рассматривать как уточнение описаний реализаций из Т^ и Т2 с использованием признака Х^.

В заключение главы рассмотрено свойство инвариантности алгоритмов группировки относительно допустимых преобразований шкал.

Определение 4. Алгоритмом группировки назовем отображение <Л. : V '—»■ В , где 9 = (гх <*> ),

Г1Г = {Х1> » РАв{А1А2»...Ак} £

И д- множество всевозможных разбиений на А, ^{Тд., Т2..... Тк}еЛ .

Для произвольной (и*) определим функцию ^со(х):

. т. если 3 т/1 < ш ^ к.х е Тт

С,Лх)-} т

ио

р I О,

если V т= 1,к, х ф Т

ш

Рассмотрим преобразование ( я/ ) = 'Р 2 (х )|—> 'РпСх" )) , где -допустимое

16

преобразование Xj , x¡ - столбец значений X. на V ; ip(u) назовем допустимым преобразованием. Преобразованной таблице f (т-**) соответствует признаковое пространство D( f (и* ) ) =Dio . После применения алгоритма jÍ к получим 'В|р=»(гд, , ) И по

аналогии с Сг ш (х) определим функцию G- (у) в пространстве D ip .

Определение 5, Алгоритм Л назовем инвариантным относительно допустимых преобразований шкал определенных типов, если для любой таблицы V , признаки которой измерены в шкалах этих типов, Vx £ D и V<p -допустимого преобразования таблицы V имеет место соотношение G- ш (х) = G (fí*)).

Для используемого класса логических функций показано, что Dip= ip (D) , а используемые критёрии инвариантны относительно допустимых преобразований шкал наименований, порядка, и более сильных количественных шкал.

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

Алгоритм ALG1 реализует процедуру последовательного построения таксонов-конъюнкций, в ходе которой длина каждой формируемой конъюнкции S увеличивается путем поочередного добавления элементарных логических функций с тем, чтобы обеспечить максимизацию критерия качества таксонов f(s) .

Алгоритм состоит из двух этапов, предварительного и основного. В ходе предварительного этапа осуществляется построение Dj(j=l, п) , а на количественных признаках дополнительно расставляются градации, определяющие некоторое начальное одномерное разбиение, с целью исключения из дальнейшего перебора заведомо неперспективных элементарных множеств. Рассмотрены

различные способы расстановки градаций, проанализированы их особенности, сильные и слабые стороны.

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

На основе теоретического и экспериментального исследования особенностей алгоритма АЬ(Зг1 сделаны следующие выводы о его применимости и свойствах:

1. Алгоритм АЬСг! ориентирован на работу в разнотипном признаковом пространстве и инвариантен к допустимым преобразованиям количественных, порядковых и • номинальных шкал.

2. Алгоритм А1/01 обеспечивает построение таксонов—конъюнкций с одновременным выделением для каждого таксона своих информативных признаков, при этом точное число таксонов заранее не фиксируется.

3. Наряду с изолированными таксонами-конъюнкциями могут быть выделены группы взаимно-пересекающихся конъюнкций, соответствующие более сложным структурам данных или объединению таких структур. В ряде случаев возможно получение информации о целесообразности их дальнейшего разбиения (изложена методика такого анализа). Для более точного описания сложных структур необходимо привлечение других алгоритмов, например, А1/ОгЗ (см. ниже).

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

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

Алгоритм АЬСг2 осуществляет построение группировки в виде бинарного дерева путем последовательного деления одного из имеющихся в текущий момент таксонов на два. На первом шаге делится единственный таксон, содержащий все реализации эмпирической таблицы. Как и в алгоритме АЬ01|присутствует предварительный этап, связанный с расстановкой градаций. Деление таксонов в процессе основного этапа алгоритма осуществляется на основе критерия р(51)+Р(32)

где: S,S^,S2 _ конъюнкции, определяющие соответственно разделяемый и образуемые при разделении таксоны;

(S-j), *) (Sg)) - монотонно возрастающая по каждому аргументу функция. Особенностью алгоритма ALG-2 является то, что на каждом шаге разбиение строится первоначально по одному из признаков, а затем оценивается качество определяемого им многомерного разбиения. Таким образом, на каждом шаге определяется признак, разбиение по которому максимально соответствует оптимальному разбиению во всем пространстве, что обеспечивает сочетание достоинств моиотетическнх и политетичес— ких алгоритмов. Так же, как и ALG 1, он инвариантен к допустимым преобразованиям шкал, позволяет строить таксоны в разных признаковых пространствах. Таксоны представляются только в виде конъюнкций. Все другие специфические- черты определяются свойством иерархичности, обеспечивающим возможность построения разбиений разного уровня генерализации. Число таксонов необходимо зафиксировать заранее на уровне максимально допустимого. Динамика изменения критериев позволяет судить о существовании оптимального (естественного) числа классов на М1к<ж< ч- гве данных.

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

Узлом дерева назовем пару и = (5(х,Т), 1 ), где Т является таксоном после некоторого шага построения дерева, "С - соответствующая группа реализаций. Рассмотрим некоторый узел Щ , не являющийся конеч-1 2

ным, и узлы И . и 1С. , полученные при его делении:

11 п

иГ(5(х,Т1) .), Зг5(х,Т1)= & 1(х,^).

1 2 ] = 1

Для XX. . и П. введем аналогичные обозначения с 1 1

верхними индексами. Конъюнкции рассматриваются в полном признаковом пространстве. Для введения локальной оценки информативности признака на 1 - ом шаге разделим множество признаков на три подгруппы:

(Х0)^-/^ = е., ,

(х1).-{х]/х. ф (х0),, а]п ^ ± 0} ,

(Х2)1 = Пс12} = 0}.

В (Х®)^ входят признаки, множества значений которых на реализациях, соответствующих Ц 1 и и, 2 г

1 1

не отличаются от множества значений для IX, ^ , в силу

чего, основываясь на , невозможно решить ни

для какой реализации из Х- ^ задачу отнесения ее к X . 2

или 1 . Назовем эти признаки локально неинформативными на 1-ом шаге. Рассуждая аналогичным образом, назовем признаки^из локально информативными,

а признаки из (X ) ) локально частично информативными. Такое разбиение определяет оценку локальной информативности признаков в шкале порялка, .Далее строится оценка информативности на всем дереве разбиений:

хО-кп1(х°), -

1=1 1

множество неинформативных признаков;

Х1=Чл1(Х1)^\Х-множество частично информативных признаков;

2 к—1 о

X = XI (X ). . - множество информативных признаков. 1=1 1

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

Пусть И- - множество

внутренних узлов дерева. Тогда множество информативных систем

[си] = .((хд,х]2.....Хд)/1 £ 1 и0(т-1^)

Зх.т(1 6 т <1), Т.ч. х.т е (х2)1т } .

Введем булевую переменную ^ 0= 1,п) :

и если Зи1теи° . т.ч. Хле(х2)1т,

} I О, в противном случае

Рассмотрим набор таких переменных .....2п)

и булевую функцию 1С (г) = &

' ш=1 . * . 2\

¡/х. е (х )]т

Справедливы следующие утверждения:

1./(г) = 1 тогда и только тогда, когда множество переменных, имеющих значение 1, соответствует некоторой информативной системе признаков.

2. .Всякая минимальная информативная система признаков определяется одним из простых импликантов сокращенной д.н.ф. ^ (г).

Рассмотрен аналогичный способ оценивания информативности признаков и для разбиений, не имеющих древообразной структуры, в частности, для алгоритма АЬСЗг1. В этом случае вместо узлов рассматриваются все пары таксонов, и. • соответствует объединяющей конъюнкции

2 Для этой пары. 2

В алгоритме АЪ02 множества (Х0)^, (X )р(Х формулируются автоматически в> процессе группировки, поэтому построение минимальных информативных систем возможно без больших дополнительных затрат. В АЬСх1 на этапе формирования конъюнкций отсекаются признаки из (Х®)[ , а разделение (Х^^и (Х^возможно с помощью дополнительных процедур анализа пар таксонов.

Алгоритмы АЬО1 и АЬСт2 позволяют осуществлять обработку таблиц с "пропусками*. Предположим, для некоторой реализации х|=(хрх2;...,хг] ) ,1 1 ^ N исследуемой эмпирической таблицы V неизвестны значения Пд < п признаков. Обозначим X' - множество измеренных, а X" - множество неизмеренных признаков. Без ограничения общности можно считать Х' = Х2..... *п-п0] • X» = {х„-п0+1,.... Хп} .

В АЬО! И АЬ(3-2 действует следующее правило обработки реализаций с пропусками: в процессе формирования конъюнкций з многомерном, признаковом пространстве информация о реализации использует-

ся при добавлении з конъюнкцию элементарных логических функции пс признакам из X1; при работе с признаками из X" реализация игнорируется (если она к тому

времени цопала в формируемый таксон, то она з нем остается, а если нет - не включается),

Опрг-ог-лечнр. Проекцией конъюнкции Э , определенной в X, на подпространство X1 называется конъюнкция » получающаяся из 3 удалением всех элементарных логических функций по признакам, не входящим в X1.

Рассмотрим проекции .....построенных

конъюнкций на подпространство О1, соответствующее X'. Пусть х:. -проекция Х| на С' , Предположим, имеется 5'(1 < 1 <к-), т.ч. З^х^Т'О = 1.

Рассмотрим соответствующую ей в исходном

признаковом пространстве:

5!(хЛЧ) = 1(х,с}Ь).

]=п-по+1

Результаты группировки позволяют также осуществлять прогнозирование отсутствующего значения

Х^ (П-Пдт1 — ] ^ п) С ТОЧНОСТЬЮ ДО МНОЖеСТва

значений^ определяемого элементарным подмножеством с^ =- dj ц 3*.

Для оценивания качества прогноза исполы)уются точность "'[(х^, Хр и наделен ость :

= (-1'Х|):=1~Р(1(х1.^ ) ) -характеризует

уменьшение неопределенности относительно диапазона возможных значений Xj у в результате сделанного

прогноза; п-п -п., п +п

к / \ и О *

ь XI) = - =1----, где

' п п

п:<- число неинформативных признаков для э' в X 1 , характеризует качество исходной для прогноза информации.

23

В диссертационной работе да;: анализ свойств этих функций, показана связь с энтропиен, рассмотрены

сложные для прогнозирования ситуации (когда нет проекции S'^ . которой принадлежит х[ и др.) и возможности их преодоления, а также те редкие случаи, когда прогнозирование невозможно,

В последнем параграфе главы Ш рассмотрен алгоритм ALG3 , основанный на использовании принципиальных идей пепараметрического алгоритма выделения кластеров (групп схожих данных), описанного в работе Mizogushi R, Shimura М. *) ■ и класса логических функций. Исходный алгоритм основан на поиске к ближайших соседей и предназначен для пространства количественных признаков, в котором он обеспечивает выделение довольно сложных. структур. В зависимости от требований, предъявляемых к точности и сложности описаний в.конкретной задаче, конъюнкции могут использоваться на разных этапах формирования групп данных, что позволяет получать итоговые таксоны в виде'дизъюнкций, разной длины. Предложены также способы расширения класса допустимых таблиц для исходного-алгоритма за счет изменения подхода к определению множества к ближайших соседей.

В главе 1У рассмотрены вопросы, связанные с практическим ярименением разработанных методов группировки. Дано общее описание структуры и возможностей пакета программ ЛОГР для решения задач группировки на РП-таблицах, в основу которого положены алгоритмы' ALG1, ALG 2 » ALG3i приведены результаты экспериментального сравнения разработанных алгоритмов с некоторыми известными алгоритмами в области применения последних.

Т)

'Mizogushi М.,Shimura S. A nonparametric algorithm for detecting clusters using hierarchical structure.//lEEE Trans.on Pattern analysis and Machine Intelligence,1980,PAMI-2,No.4-p. 292-300.

Для сравнения в пространстве количественных признаков был изят алгоритм "Форэль", в пространстве булевых признакоз использовались результаты алгоритма, списанного в работе Дородницына A.A., Каспшнцкои М.Ф., и Сергиенко И.В. *'') и алгоритма, основанного на методе вычисления оценок ***) , Сравнение проводилось на тестовых задачах и реальных, данных с известной структурой. Оно показало, что далее в тех случаях, когда донные не обладают всей спецификой РП-таблнц, разработанные алгоритмы, основанные на логических функциях, в целом не уступают по качеству указанным выше алгоритмам сравнения.

Программное обеспечение, реализованное в виде пакета программ ЛОГР, применялось при решении ряда прикладных задач, связанных с управлением в технических системах и автоматизацией обработки данных в научно-практических исследованиях. Подробно рассмотрено применение разработанных методов и алгоритмов в процессе автоматизированной обработки данных дистанционного зондирования с целью индикации повре;кдснной лесной растительности и при решении задачи медицинской диагностики - выявление закономерностей протекания инфаркта миокарда с целью прогнозирования исхода и отдаленных последствий заболевания.

""') Дородницын А.А,,Каспшицкая М.Ф., Сергиенко И.В.

Об одном подходе к формализации классификации.//Кибер-

нетика, 1976, №'6, стр. 132-140. -х-*-* )

Эшанкулов Т. Адаптивные алгоритмы вычисления оценок в задачах таксономии и выделения особенностей: Дисс.капд.техн.наук: 05.13.01, Ташкент, 1984.

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

1. На основе анализа существующих постановок задач автоматической классификации (таксономии, кластерного анализа, группировки объектов и т.д.) и методов' их решения сформулирована постановка задачи, наиболее адекватная классу РП-таблиц.

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

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

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

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

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

7. Разработано программное .обеспечение, реализующее алгоритмы группировки, основанные на логических функциях (пакет программ ЛОГР), которое использовано при решении важных прикладных задач, связанных с управлением техническими енстемдмл и автоматизированной обработкой данных в научно-практических исследованиях.

Основные результаты диссертации опубликованы в следующих ¡заботах:

1.4Г.С.Лбов, Т.М.Пестунова. Логические функции в задачах группировки объектов^/ Программно—алгоритмическое обеспечение прикладного многомерного статистического анализа: Тез. Всес, школы-семинара - М.,1983, С.83-84.

2. Г.С.Лбов, Т.М,Пестунова. Группировка объектов в пространстве разнотипных признаков.// Анализ нечисловой информации в социологических исследованиях. -М.:Наука, 1985, С.141-149.

3. Т.МЛестунова, Об одном методе группировки с использованием логических функций.// Логико-комбинаторные методы в искусственном интелекте и распознавании образов: Тез.Реслубл. школы-семинара, Кишинев, 1985, С. 55-56.

4., Т.М.Пестунова. О свойствах одного метода группировки, основанного на логических функциях.// Непараметрические и робастные методы статистики в кибернетике. -Томск, 1985, С.,298-306..

5..Т.М.Пестунова. Об инвариантности алгоритмов группировки.// Математическое и программное обеспечение многомерного статктического анализа данных: Тез. Республ. конф,- Минск,1985, С.113.

6. Г.С.Лбов, Т.М.Пестунова . Построение дерева разбиений в задаче группировки объектов с использованием логических функций.// Вычислительные системы. -Вып. 117 - 1986 - С. 63-77.

7. Т.М.Пестунова . Об одном подходе к решению задачи группировки с использованием логических функций. // Оперативно-информационный выпуск (препринт № 2: ВЦ СО АН СССР) - Красноярск, 1983, С.28-33.

8. Т.М.Пестунова. Пакет программ ЛОГР для решения задачи группировки объектов.// Применение многомерного статистического анализа в экономике И оценке качества продукции,-Тарту, 1989, -С.228-229.

Э^Гафаров В.8., Гаткин Я.Ш., Псстунова Т.М. Прогнозирование отдаленных последствий у болькых, перенесших инфаркт млоклрда. (Методические рекомендации) -Новосибирск, 1989 - 13 с.

10. Т.М.Пестунова. Об использовании логических функций для выделения сложных структур в задаче группировки объектов (кластерного анализа)// Математическое и программное обеспечение анализа данных.:Тез, Республ. конф. - Минск, 1990 - С. 57.

11. Т.М.Пестунова. Дерево разбиений в задаче группировки объектов и оценивании информативности разнотипных признаков.// Применение статистических методов в производстве и управлении; Тез. Всес. научно-техн. конф. с междунар. участием.-Пермь, 1990 -

С. 333-334.

12. Т.М.Пестунова. Оценивание информативности признаков и прогнозирование пропущенных значений в процессе решения задачи автоматической классификации (группировки) разнотипных данных.// Теория и практика классификации и систематики в народном хозяйстве: Тез. Всес. научно-техн, симп. - Москва, 1990 - стр. 95-96,

Подписано к печати 11 марта 1992г. Формат 84x63x1/16 Бумага оберточная. Тираж 100 экз. Усл. печ. л. 1. Уч. -изд. л. 1.

заказ № 6 О 8

Бесплатно

Отпечатано в типографии ПО НПЗ