Модификация метода логического анализа данных для задач классификации

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

Р.И. Кузьмич, И.С. Масич

МОДИФИКАЦИИ МЕТОДА 
ЛОГИЧЕСКОГО АНАЛИЗА ДАННЫХ 
ДЛЯ ЗАДАЧ КЛАССИФИКАЦИИ

 

Министерство науки и высшего образования Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
 
Р.И. Кузьмич, И.С. Масич 
 
МОДИФИКАЦИИ МЕТОДА 
ЛОГИЧЕСКОГО АНАЛИЗА ДАННЫХ 
ДЛЯ ЗАДАЧ КЛАССИФИКАЦИИ 
 
Монография 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2018 

 
 

УДК 519.677 
ББК 22.161 
К893 
 
Р е ц е н з е н т ы: 
Л. А. Казаковцев, доктор технических наук, профессор Сибирского гос
ударственного аэрокосмического университета им. акад. М. Ф. Решетнева; 

А. В. Наумов, доктор физико-математических наук, профессор Мос
ковского авиационного института 
 
Кузьмич, Р. И. 
К893  
Модификации метода логического анализа данных для задач 
классификации : монография / Р. И. Кузьмич, И. С. Масич. – Красноярск: Сиб. федер. ун-т, 2018. – 180 с. 
 
ISBN 978-5-7638-3698-1 
 
 
Рассмотрены логические алгоритмы классификации, позволяющие получать интерпретируемые и обоснованные решения практических задач распознавания. Особое внимание уделено методу логического анализа данных и его модификациям, направленным на улучшение интерпретируемости и обобщающих 
способностей классификатора. 
Предназначена для научных работников и специалистов, занимающихся 
вопросами применения методов классификации при решении практических  
задач распознавания. Может быть полезна студентам и аспирантам, специализирующимся в области математического моделирования и информационных  
систем. 
 
 
Электронный вариант издания см.:  
  УДК 519.677 
http://catalog.sfu-kras.ru  
  ББК 22.161 
 
 
 
 
 
 
 
 
 
 
ISBN 978-5-7638-3698-1 
 
 
© Сибирский федеральный университет, 2018 

– 3 – 

ОГЛАВЛЕНИЕ 
 
 
 
ПРЕДИСЛОВИЕ ............................................................................................... 6 

ВВЕДЕНИЕ ......................................................................................................... 7 

1. АНАЛИЗ ЛОГИЧЕСКИХ АЛГОРИТМОВ КЛАССИФИКАЦИИ ..... 8 
1.1. ОСНОВНЫЕ  ПОНЯТИЯ  ЛОГИЧЕСКИХ  АЛГОРИТМОВ  
КЛАССИФИКАЦИИ ............................................................................... 8 
1.2. АЛГОРИТМЫ  ПОИСКА  ЗАКОНОМЕРНОСТЕЙ  В  ФОРМЕ  
КОНЪЮНКЦИЙ .................................................................................... 11 
1.3. АНАЛИЗ  ОСНОВНЫХ  ЛОГИЧЕСКИХ  АЛГОРИТМОВ  
КЛАССИФИКАЦИИ  И  СПОСОБОВ  ИХ  ПОСТРОЕНИЯ ........... 16 
1.3.1. Решающие списки ....................................................................... 16 

1.3.2. Решающие деревья ...................................................................... 19 

1.3.3. Алгоритмы простого и взвешенного голосования правил ..... 23 

1.3.4. Алгоритмы вычисления оценок................................................. 29 

1.4. АНАЛИЗ  ПРОГРАММНЫХ  СИСТЕМ  ДЛЯ  РЕШЕНИЯ  
ЗАДАЧ  КЛАССИФИКАЦИИ.............................................................. 34 

2. ПРЕДМЕТНЫЕ  ОБЛАСТИ  ПРИМЕНЕНИЯ  ЛОГИЧЕСКИХ  
АЛГОРИТМОВ  КЛАССИФИКАЦИИ .................................................. 41 
2.1. ПРИЛОЖЕНИЯ  В  ОБЛАСТИ  БИЗНЕСА,  ЭКОНОМИКИ   
И  ФИНАНСОВ ...................................................................................... 41 
2.2. ПРИЛОЖЕНИЯ  В  ОБЛАСТИ  МЕДИЦИНЫ  И  
ЗДРАВООХРАНЕНИЯ ......................................................................... 43 
2.3. ПРИЛОЖЕНИЯ  В  ОБЛАСТИ  ТЕХНИКИ ....................................... 45 
2.4. ПРИЛОЖЕНИЯ  В  ОБЛАСТИ  ФИЗИКИ,  ХИМИИ,  БИОЛОГИИ46 
2.5. ПРИЛОЖЕНИЯ  В  ОБЛАСТИ  ОБРАБОТКИ  И  
РАСПОЗНАВАНИЯ  ИЗОБРАЖЕНИЙ .............................................. 48 
2.6. СРАВНИТЕЛЬНЫЙ  АНАЛИЗ  ЛОГИЧЕСКИХ  АЛГОРИТМОВ  
КЛАССИФИКАЦИИ ............................................................................. 49 

3. МЕТОД  ЛОГИЧЕСКОГО  АНАЛИЗА  ДАННЫХ  И  ЕГО  
МОДИФИКАЦИИ ...................................................................................... 58 
3.1. ОПИСАНИЕ  ПОДХОДА ..................................................................... 58 
3.2. БИНАРИЗАЦИЯ  ПРИЗНАКОВ .......................................................... 59 

– 4 – 

3.3. ПОСТРОЕНИЕ ОПОРНОГО МНОЖЕСТВА ..................................... 61 
3.4. ФОРМИРОВАНИЕ  ЗАКОНОМЕРНОСТЕЙ ..................................... 63 
3.5. ПОСТРОЕНИЕ  КЛАССИФИКАТОРА .............................................. 66 
3.6. МОДИФИКАЦИИ  ДЛЯ  МЕТОДА  ЛОГИЧЕСКОГО   
АНАЛИЗА  ДАННЫХ........................................................................... 67 
3.7. РЕШЕНИЕ  ЗАДАЧ  ПСЕВДОБУЛЕВОЙ  ОПТИМИЗАЦИИ ......... 73 

4. ПОИСКОВЫЕ  АЛГОРИТМЫ  УСЛОВНОЙ  ПСЕВДОБУЛЕВОЙ  
ОПТИМИЗАЦИИ ........................................................................................ 78 
4.1. СОСТОЯНИЕ  ПРОБЛЕМЫ ................................................................. 78 
4.2. СВОЙСТВА  ПСЕВДОБУЛЕВЫХ  ФУНКЦИЙ ................................ 84 
4.3. ПОСТАНОВКА  ЗАДАЧИ  УСЛОВНОЙ  ПСЕВДОБУЛЕВОЙ  
ОПТИМИЗАЦИИ .................................................................................. 89 
4.4. ТОЧНЫЕ  АЛГОРИТМЫ  УСЛОВНОЙ  ПСЕВДОБУЛЕВОЙ  
ОПТИМИЗАЦИИ .................................................................................. 91 
4.5. ПРИБЛИЖЕННЫЕ  АЛГОРИТМЫ  УСЛОВНОЙ  
ПСЕВДОБУЛЕВОЙ  ОПТИМИЗАЦИИ ........................................... 100 

5. АНАЛИЗ  ИСХОДНОЙ  ВЫБОРКИ  ДАННЫХ ................................ 105 
5.1. НЕДОСТАТКИ  В  ИСХОДНОЙ  ВЫБОРКЕ  ДАННЫХ ............... 105 
5.2. ВЫБОР  ПОДМНОЖЕСТВА  ПРИЗНАКОВ  ДЛЯ  
КЛАССИФИКАЦИИ  С  ВЫСОКОЙ  ТОЧНОСТЬЮ .................... 108 
5.3. ВЫБОР  ПУЛА  ПРИЗНАКОВ ........................................................... 110 
5.4. АЛГОРИТМИЧЕСКАЯ  ПРОЦЕДУРА  ПОЛУЧЕНИЯ  
УСЕЧЕННОГО  НАБОРА  ПРИЗНАКОВ ........................................ 113 

6. ПРОГРАММНАЯ  РЕАЛИЗАЦИЯ  МЕТОДА  
И  ЭКСПЕРИМЕНТАЛЬНЫЕ  ИССЛЕДОВАНИЯ   
НА  ПРАКТИЧЕСКИХ  ЗАДАЧАХ ....................................................... 115 
6.1. ПРОГРАММНАЯ  РЕАЛИЗАЦИЯ  МЕТОДА  ЛОГИЧЕСКОГО  
АНАЛИЗА  ДАННЫХ  И  ОСОБЕННОСТИ  ИСПОЛЬЗОВАНИЯ  
ПРОГРАММНОЙ  СИСТЕМЫ .......................................................... 115 
6.2. РЕЗУЛЬТАТЫ  ЭКСПЕРИМЕНТАЛЬНЫХ  ИССЛЕДОВАНИЙ  
МЕТОДА ЛОГИЧЕСКОГО АНАЛИЗА ДАННЫХ И 
РАЗРАБОТАННЫХ ДЛЯ НЕГО МОДИФИКАЦИЙ  НА  
ПРАКТИЧЕСКИХ  ЗАДАЧАХ  КЛАССИФИКАЦИИ ................... 120 
6.3. НАСТРОЙКА  ПАРАМЕТРОВ  МЕТОДА  ЛОГИЧЕСКОГО  
АНАЛИЗА  ДАННЫХ  С  УЧЕТОМ  СПЕЦИФИКИ  РЕШАЕМЫХ  
ЗАДАЧ .................................................................................................. 135 

– 5 – 

6.4. СРАВНИТЕЛЬНЫЙ  АНАЛИЗ  МЕТОДА  ЛОГИЧЕСКОГО  
АНАЛИЗА  ДАННЫХ  С  ДРУГИМИ  АЛГОРИТМАМИ  
КЛАССИФИКАЦИИ  НА  ПРАКТИЧЕСКИХ  ЗАДАЧАХ ............ 137 

ЗАКЛЮЧЕНИЕ ............................................................................................. 146 

СПИСОК  ЛИТЕРАТУРЫ .......................................................................... 148 

ПРИЛОЖЕНИЕ 1 .......................................................................................... 166 

ПРИЛОЖЕНИЕ 2 .......................................................................................... 174 
 
 
 
 
 

– 6 – 

ПРЕДИСЛОВИЕ 

 
 
Настоящее исследование направлено на разработку модификаций 
для метода логического анализа данных, позволяющих улучшить интерпретируемость и обобщающие способности классификатора. 
Первая глава посвящена обзору наиболее распространенных логических алгоритмов классификации, алгоритмов поиска закономерностей  
в форме конъюнкций для них, а также анализу основных программных систем, решающих задачи классификации. 
Во второй главе приведены примеры практического применения логических алгоритмов классификации в различных предметных областях,  
а также апробация и настройка алгоритмов J48, RandomTree, DecisionTable, 
OneR, реализованных в программе WEKA, на задачах диагностики болезни 
Паркинсона и колик у лошадей. 
Третья глава посвящена описанию основных этапов метода логического 
анализа данных, созданию оптимизационных моделей для формирования закономерностей и разработке алгоритмических процедур, позволяющих улучшить 
интерпретируемость классификатора, сократив количество правил в нем. 
В четвертой главе рассматриваются задачи оптимизации вещественных функций бинарных переменных, так называемые задачи псевдобулевой 
оптимизации. Разработанные алгоритмы применяются для нахождения  
логических закономерностей (используемых для построения классификаторов) в данных, что представляет собой задачу условной псевдобулевой оптимизации большой размерности. 
В пятой главе рассмотрена проблема возможного присутствия недостатков в исходной выборке данных (ошибки классификации, пропущенные значения признаков, погрешности при измерении значений числовых 
признаков) и предложены методы, позволяющие избежать проблем обработки данных при наличии данных недостатков. Также в главе решена  
задача выбора множества признаков, которая с высокой точностью разделяет положительные и отрицательные наблюдения.  
Шестая глава посвящена программной реализации метода логического 
анализа данных и экспериментальным исследованиям на практических задачах. 
В заключении сформулированы основные выводы и результаты исследования, имеющие самостоятельное научное и практическое значение. 
В прил. 1 описана база данных, содержащая исходные данные по задаче прогнозирования осложнений инфаркта миокарда. 
В прил. 2 описаны результаты выявления наиболее и наименее значимых для распознавания признаков в задаче прогнозирования осложнений инфаркта миокарда. 

– 7 – 

ВВЕДЕНИЕ 

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

– 8 – 

1. АНАЛИЗ  ЛОГИЧЕСКИХ  АЛГОРИТМОВ  
КЛАССИФИКАЦИИ 

 
 
 
 
1.1. ОСНОВНЫЕ  ПОНЯТИЯ  
ЛОГИЧЕСКИХ  АЛГОРИТМОВ  КЛАССИФИКАЦИИ 
 
 
Пусть φ: X → {0, 1} – некоторый предикат, определённый на множестве наблюдений X. Предикат φ покрывает наблюдение x, если φ(x) = 1. 
Предикат называют закономерностью, если он покрывает достаточно много наблюдений одного класса и практически не покрывает наблюдения 
других классов [26]. 
Любая закономерность классифицирует только часть наблюдений  
из множества X. Объединив определённое количество закономерностей  
в композицию, можно получить классификатор, способный классифицировать любые наблюдения из множества. Логическими алгоритмами классификации будем называть композиции, состоящие из легко интерпретируемых закономерностей [17]. 
Класс, на базе наблюдений которого построена закономерность,  
будем называть своим классом. Чем больше наблюдений своего класса  
по сравнению с наблюдениями всех других классов покрывает закономерность, тем она информативнее. Наблюдения своего класса называют также 
положительными, а других – отрицательными. Покрытие отрицательного 
наблюдения является ошибкой закономерности, непокрытие положительного наблюдения считается ошибкой менее критичной, поскольку от закономерностей не требуется покрывать все наблюдения. Наблюдение, не покрытое одной закономерностью, может быть покрыто другой.  
Для определения ε-, δ-закономерности вводятся следующие обозначения: 
Pk – число наблюдений своего класса k в выборке Xℓ, где Pk > 1,  
Pk + Nk = ℓ; 
pk(φ) – из них число наблюдений, для которых выполняется условие 
φ(x) = 1; 
Nk – число наблюдений всех остальных классов в выборке Xℓ, где Nk > 1; 
nk(φ) – из них число наблюдений, для которых выполняется условие 
φ(x) = 1. 
Задача построения информативной закономерности состоит в оптимизации по двум критериям: pk(φ) → max и nk(φ) → min. Наименее пригодны с точки зрения классификации те закономерности, которые либо  

– 9 – 

покрывают слишком мало наблюдений, либо покрывают положительные  
и отрицательные наблюдения примерно в той же пропорции, в которой они 
были представлены во всей выборке. 
Далее вводятся обозначения Ek для доли отрицательных среди всех 
покрываемых наблюдений и Dk для доли покрываемых положительных 
наблюдений: 
 


 
 
 






k
k

k
k
n
p
n
X
E

,
,  
 


 
 
 






k
k

k
k
n
p
p
X
D

,
. 

 
Закономерность φ называется логической ε-, δ-закономерностью для 
класса k, если Ek(φ,Xℓ) ≤ ε и Dk(φ,Xℓ) ≥ δ при заданных достаточно малом ε  
и достаточно большом δ из отрезка [0, 1]. 
Закономерность φ называется чистой или непротиворечивой, если 
nk(φ) = 0. Если nk(φ) > 0, то закономерность φ называется частичной [17].  
Если длина выборки мала или данные практически не содержат шума, тогда лучше искать чистые закономерности для подобного рода задач. 
Например, при классификации месторождений редких полезных ископаемых по данным геологоразведки, где данные стоят дорого, а потому, как 
правило, тщательно проверяются. Но чаще данные оказываются неполными 
и неточными, например в медицинских и экономических задачах. Для них 
вполне допустима незначительная доля ошибок на обучающей выборке. 
При решении таких задач лучше использовать частичные закономерности.  
Для целенаправленного поиска лучших закономерностей удобнее 
иметь скалярный критерий информативности. Одним из таких критериев 
является статистический критерий информативности [17]. Пусть X – вероятностное пространство, выборка Xℓ – случайная, независимая, одинаково 
распределённая, y*(x) и φ(x) – случайные величины. Допускается справедливость гипотезы о независимости событий {x: y*(x) = k} и {x: φ(x) = 1}.  
Тогда вероятность реализации пары (p, n) подчиняется гипергеометрическому распределению [148]: 
 



n
p
N
P

n
N
p
P
N
P
C

C
C
n
p
h



,
,
 , 
 
 
 
  (1.1) 

 

где 

!
!
!
k
m
k
m
С k
m


– биномиальные коэффициенты; 0 ≤ k ≤ m; 0 ≤ p ≤ P;  

0 ≤ n ≤ N. 
Если вероятность (1.1) мала, а пара (p, n) реализовалась, то гипотеза 
о независимости должна быть отвергнута. Чем меньше значение вероятности, тем более значимой является связь между y* и φ.