Извлечение и неизбыточное представление закономерностей в многомерных данных

Актуальность темы исследования. Современные методы интеллекту- ального анализа данных ориентированы на исследование многомерных и разнотипных данных с целью выявления знаний в виде закономерностей. Значительный вклад в развитие интеллектуального анализа данных внесли российские ученые: Ю.И. Журавлев (алгебраическая теория распознавания), Г.С. Лбов (логические методы распознавания), К.В. Рудаков (алгебраический синтез корректных алгоритмов), В.Н. Вапник, А.Я. Червоненкис (статистиче- ская теория обучения), Н.Г. Загоруйко (когнитивный подход, FRiS-функции), С.О. Кузнецов, М.И. Забежайло (оценки сложности ДСМ-процедур) и др.
Средством описания причинно-следственных закономерностей в мно- гомерных данных, представленных матрицей «объектпризнак», служат ас- социативные правила, отражающие, какие признаки, события или явления появляются вместе и насколько часто это происходит. Широкий интерес к этому классу закономерностей начался со статьи R. Agrawal, T. Imielinski, A. Swami, опубликованной в 1993 году, и с тех пор ежегодно появляются не- сколько сотен публикаций, содержащих новые методы и алгоритмы извлече- ния ассоциативных правил. Для многих приложений наиболее значимы стро- гие ассоциативные правила – правила с единичной достоверностью. Напри- мер, они широко востребованы при решении задач клинической диагностики. В национальном проекте «Электронное здравоохранение», утвержденном Президиумом Совета при Президенте Российской Федерации по стратегиче- скому развитию и приоритетным проектам (протокол No 9 от 25.10.2016 г.) отмечается, что для повышения эффективности оказания медицинской по- мощи гражданам необходимо широкое внедрение в организации здравоохра- нения новейших лечебно-диагностических информационных технологий, ба- зирующихся на интеллектуальном анализе данных [73].
В настоящее время практическое применение ассоциативных правил (АП) во многом ограничивается проблемой размерности [2, 7, 17, 22]. Число
5
АП, извлекаемых современными методами анализа данных, часто достигает несколько десятков тысяч. Это существенно усложняет их интерпретацию и снижает степень доверия пользователя к полученным результатам. Для ре- шения данной проблемы применяются два подхода: фильтрация с помощью мер значимости и когнитивный подход. Меры значимости позволяют чис- ленно оценивать достоверность и поддержку АП и предъявлять пользовате- лю только те из них, для которых значения мер значимости превышают уста- новленные пороговые значения. Когнитивный подход предполагает создание базисов как «сжатых» форм представления множества искомых АП. Между тем, оба подхода не исключают появление в результирующем множестве из- быточных правил. Ассоциативное правило принято считать избыточным, ес- ли его удаление из множества выявленных правил не приводит к потере ин- формации об ассоциациях между анализируемыми данными. Формальное определение избыточности предполагает уточнение, какая именно информа- ция не должна быть утеряна. Для строгих АП такой информацией, прежде всего, служит уровень или порог поддержки  величина, характеризующая минимальную представительность этих правил в анализируемых данных.
Степень разработанности темы исследования. На сегодняшний день наиболее развиты методы формирования базисов строгих АП. В них под ба- зисом понимается минимальное в некотором смысле множество строгих АП с заданным уровнем поддержки. Особого внимания заслуживают методы и алгоритмы построения канонического и минимаксного базисов, основанные на алгебраическом подходе, разработанном группой ученых под руково- дством Р. Вилле и известном в литературе как анализ формальных понятий [95, 116, 117].
Канонический базис (базис Дюкена-Гига) создается из минимального числа строгих ассоциативных правил, рекуррентно задаваемых в терминах псевдосодержаний. Этот базис достаточно полно изучен в работах B. Ganter, V. Duquenne, S. Rudolph, С.О. Кузнецова, С.А. Объедкова [95, 107109, 112, 116, 120, 128].

6
Минимаксный базис формируется из строгих АП, имеющих минималь- ную посылку и максимальное следствие. Именно такие АП интересны для клинической диагностики, поскольку каждое из них может определять ми- нимальный набор симптомов заболевания и максимальный набор признаков, задающих его последствия. Другой аргумент в пользу выбора минимаксного базиса для клинической диагностики – это наличие хорошо апробированных практикой алгоритмов его построения. В их числе различные версии алго- ритма Close, представленные и изученные в работах M.J. Zaki, C.J. Hsiao, T. Uno, T. Asai, Y. Uchida, H. Arimura [93, 114, 127, 132].
Вычислительные эксперименты показали, что канонические и мини- максные базисы могут содержать избыточность, устранение которой – это дополнительный шаг, позволяющий сокращать число строгих АП, предъяв- ляемых пользователю для интерпретации. С этой целью представляет инте- рес использование выводимостей Армстронга [83]. Известно, что строгие АП подчиняются шести выводимостям Армстронга, которые позволяют порож- дать из одних правил другие правила [60]. Однако в общем случае выводи- мости Армстронга не гарантируют сохранение заданного уровня поддержки (далее кратко сохранение поддержки). Как отмечали в своих работах J.L. Balcazar, N. Pasquier, Y. Bastide, R. Taouil и L. Lakhal, именно этим огра- ничивалось применение выводимостей Амстронга для базисов строгих АП [87,115]. Поэтому актуальны исследования выводимостей Амстронга с по- мощью анализа формальных понятий и выявление среди них тех, которые сохраняют поддержку АП, и с помощью которых можно устранять избыточ- ность в минимаксном базисе при его построении, а далее при необходимости порождать из него строгие АП с сохранением поддержки.
Цель и задачи. Целью диссертационной работы является повышение эффективности анализа данных при решении задач клинической диагностики путем установления для строгих ассоциативных правил набора выводимо- стей, гарантирующих сохранение поддержки, и разработка на их основе ма- тематического и программного обеспечения.

7
Поставленная цель достигается путем решения следующих задач:
1. Установить свойства строгих ассоциативных правил и получить на- бор выводимостей, гарантирующих сохранение поддержки этих правил. Раз- работать и теоретически обосновать метод построения неизбыточного мини- максного базиса строгих ассоциативных правил.
2. Разработать алгоритм, реализующий метод построения неизбыточно- го минимаксного базиса строгих ассоциативных правил.
3. Сформировать набор средств снижения размерности матрицы «объ- ектпризнак», позволяющих уменьшать число искомых ассоциативных пра- вил.
4. Разработать программное обеспечение, реализующее алгоритмы вы- явления строгих ассоциативных правил, построения неизбыточного мини- максного базиса, а также снижения размерности матрицы «объектпризнак».
5. Провести экспериментальные исследования по оценке результатив- ности разработанных метода, алгоритмов и программ на медицинских дан- ных.
Научная новизна.
1. Разработан и теоретически обоснован новый метод построения неиз- быточного минимаксного базиса строгих ассоциативных правил. В отличие от существующих метод позволяет устранять ту избыточность в минимаксном базисе, которые не способны удалять другие методы, сохра- няя при этом поддержку строгих ассоциативных правил.
2. Разработан новый алгоритм извлечения строгих ассоциативных пра- вил и представления их в форме неизбыточного минимаксного базиса. Алго- ритм расширяет возможности известного алгоритма Close путем включения в него процедур по удалению из искомого множества зависимостей тех ассо- циативных правил, которые распознаны как избыточные, без дополнительно- го обращения к анализируемому набору данных.

8
Методы исследования. Для решения поставленных в работе задач ис- пользовались методы анализа формальных понятий, статистические методы и методы объектно-ориентированного программирования.
Теоретическая значимость работы. Предложенный в работе метод построения неизбыточного минимаксного базиса быть использован для даль- нейшего развития раздела интеллектуального анализа данных, связанного с извлечением закономерностей в данных и устранением избыточности в их представлении.
Практическая значимость работы. Применение результатов диссер- тационной работы в практическом здравоохранении позволяет повысить уро- вень информатизации клинической работы врачей, содействует верной и оперативной диагностике заболеваний. Результаты диссертационной работы могут быть также применены для тех приложений, где требуется высокая степень достоверности установленных ассоциативных правил и важна их «сжатая» форма представления, например, в информационной безопасности и анализе компьютерных сетей.
Положения, выносимые на защиту.
1. Доказательство выводимостей Армстронга с помощью анализа фор- мальных понятий и установление среди них тех выводимостей, которые со- храняют поддержку строгих ассоциативных правил.
2. Метод построения неизбыточного минимаксного базиса строгих ас- социативных правил.
3. Алгоритм формирования неизбыточного минимаксного базиса стро- гих ассоциативных правил, устраняющего избыточность из минимаксного базиса в процессе его построения без дополнительного обращения к анализи- руемому набору данных.