Supervised classification problem: new models of logical correctors

Full Text

Введение. Задача корректной классификации на основе прецедентов рассматривается в следующей постановке.

Исследуется множество объектов M. Каждый объект этого множества может быть представлен в виде числового набора, полученного на основе наблюдения или измерения ряда его характеристик x₁, ..., x_n, называемых признаками. Предполагается, что каждый признак имеет ограниченное множество допустимых значений, которые кодируются целыми числами. Известно, что M представимо в виде объединения непересекающихся подмножеств K₁, ..., K_l, l ≥ 2, называемых классами. Имеется конечный набор объектов множества M, про каждый из которых известно, какому классу он принадлежит. Это прецеденты, или обучающие объекты. Требуется по предъявленному набору значений признаков, описывающему некоторый объект из M, определить (распознать) класс, которому принадлежит этот объект.

Логический или дискретный подход к задаче классификации по прецедентам возник в связи с необходимостью прогнозировать редкие события, для которых нет достаточного статистического материала. Фундаментальную роль в создании отечественных методов логической классификации сыграли работы член-корр. РАН С.В. Яблонского, в которых введено хорошо известное в дискретной математике понятие теста [1], и работы акад. РАН Ю.И. Журавлева, опубликованные в 70–80-х гг. прошлого века. Дальнейшее развитие направление получило в большом числе публикаций, среди которых статьи [2–4] имеют непосредственное отношение к исследованиям, проводимым в данной статье.

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

Основным понятием логического подхода является понятие элементарного классификатора. Пусть N_j, j = $\overline{1, n}$, – множество допустимых значений признака x_j; H – набор из r различных признаков вида H = {x_j1, ..., x_jr}; $\sigma = ({\sigma }_1, ..., {\sigma }_r)$ – набор, в котором ${\sigma }_i \in N_{ji}$ при i = $\overline{1, r}$. Пара ($\sigma$, H) называется элементарным классификатором (ЭК) ранга r. ЭК ($\sigma$, H) может быть задан в виде элементарной конъюнкции $B_{ \left(\sigma , H\right) }=x_{j_1 }^{{\sigma }_1} \&\dots \& x_{j_r }^{{\sigma }_r}$ над переменными x₁, ..., x_n. Если объект S из M имеет признаковое описание (a₁, ..., a_n), в котором a_j, j =$\overline{1, n}$, – значение признака x_j для объекта S, и a_ji = $\sigma$_i при i =$\overline{1, r}$, то говорят, что ЭК ($\sigma$, H) содержится в объекте S. В этом случае интервал истинности конъюнкции B_{($\sigma$, H)} содержит S. ЭК называется корректным для класса K, K ∈ {K₁, ..., K_l}, если не существует двух прецедентов, содержащих данный ЭК, при этом один из этих прецедентов принадлежит K, а второй не принадлежит K.

В классических моделях в процессе обучения строятся семейства корректных ЭК. На этапе классификации каждый найденный ЭК участвует в процедуре голосования и формирования оценок принадлежности распознаваемого объекта к классам. Трудными являются задачи, в которых практически каждый корректный ЭК содержится в небольшом числе прецедентов. Подобная ситуация возникает, например, в случае, когда признаки имеют много значений. В работе [2] предложены модели логических корректоров, в которых используются идеи алгебраического подхода [5–7] к синтезу корректных классификаторов. В данном случае в качестве базовых алгоритмов рассматриваются произвольные ЭК, а в качестве корректирующих функций – булевы функции.

Логический корректор основан на построении семейства корректных наборов ЭК. Корректный для класса K набор ЭК позволяет различать любую пару прецедентов, один из которых принадлежит классу K, а другой не принадлежит этому классу, поскольку этот набор содержит ЭК ($\sigma$, H), обладающий свойством: конъюнкция B($\sigma$, H) принимает разные значения на данных объектах. Более эффективны модели логических корректоров, использующие в качестве корректирующей функции монотонную булеву функцию. Каждый монотонный корректор класса K рассматривает только те ЭК, которые содержатся в прецедентах из K.

Основная проблема, возникающая при синтезе монотонного логического корректора класса K, – это вычислительная сложность этапа обучения, на котором решается задача поиска минимальных покрытий булевой матрицы L_K значительных размеров. Каждая строка этой матрицы порождается парой прецедентов, один из которых принадлежит K, а другой не принадлежит K. Число столбцов в L_K равно числу тех ЭК, каждый из которых содержится в хотя бы одном обучающем объекте класса K. В простейшем случае, а именно когда признаки бинарные и рассматриваются только ЭК ранга 1, число столбцов в L_K равно 2n, где n – число признаков. В работе [3] построена и исследована модель логического корректора с монотонными корректными наборами ЭК ранга 1 и с применением генетического алгоритма для поиска минимальных покрытий матрицы L_K.

Для сокращения временных затрат в случае бинарных данных в работе [2] предложено осуществлять поиск монотонных корректных наборов из ЭК ранга 1 на основе построения специального вида покрытий булевой матрицы с тем же числом строк, что и в L_K, и с числом столбцов, равным числу признаков n. Однако в работе [2] не было приведено экспериментальных данных, подтверждающих существенное сокращение перебора. Эта идея обобщена в настоящей работе на случай целочисленных данных. Проведенные исследования показали эффективность подхода. Рассмотрены вопросы разработки стохастических моделей логических корректоров и модификации этих моделей на случай, когда на множествах значений признаков заданы конечные частичные порядки, т.е. признаковые описания прецедентов – это элементы декартова произведения конечных частичных порядков. Классические модели логических классификаторов над произведением частичных порядков впервые построены в работе [8].

1. Логические классификаторы: принципы работы и основные модели. Среди классических моделей логических классификаторов хорошие результаты на данных с малой значностью признаков показывают модели, в которых в качестве корректных ЭК рассматриваются представительные ЭК классов.

ЭК ($\sigma$, H) называется представительным для класса K, K ∈ {K₁, ..., K_l}, если ($\sigma$, H) содержится в хотя бы одном прецеденте из K и не содержится ни в каком прецеденте не из K. Понятие представительного ЭК введено в работе [9]. Согласно общей схеме работы рассматриваемых моделей [10], на этапе обучения задается некоторый частичный порядок на множестве P(K) представительных ЭК класса K и ищутся максимальные относительно заданного порядка элементы этого множества.

Пусть на P(K) установлен порядок, согласно которому ЭК ($\sigma$′, H ′) следует за ЭК ($\sigma$, H), если интервал истинности конъюнкции B_{($\sigma$′, H ′)} содержит интервал истинности конъюнкции B_{($\sigma$, H)}. Иначе ($\sigma$′, H ′) и ($\sigma$, H) несравнимы. Тогда максимальные элементы частично упорядоченного множества P(K) называются тупиковыми представительными ЭК.

Решающее правило основано на процедуре “голосования”, в которой участвуют найденные представительные ЭК классов [11]. Процедура “голосования” заключается в следующем. Если представительный ЭК ($\sigma$, H) класса K содержится в распознаваемом объекте S, то ($\sigma$, H) дает положительную оценку Г_K(S, $\sigma$, H) за принадлежность S к классу K, которая равна числу прецедентов, содержащих ($$, H). В противном случае ${Г}_K\left(S,\sigma ,H\right)=0$. Оценки, поданные представительными ЭК класса K за принадлежность S к этому классу, суммируются, и суммарная оценка делится на число прецедентов класса K. Объект S относится к классу, получившему наибольшую оценку. Если таких классов несколько, то происходит отказ от распознавания объекта S.

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

Один из этих способов заключается в выполнении “корректной” перекодировки исходных признаков с целью понизить их значность [12]. В результате после перекодирования объекты из разных классов остаются различимыми. Основная проблема – выбор функционала, характеризующего качество перекодировки. Построение наилучшей в смысле качества распознавания корректной перекодировки – труднорешаемая оптимизационная задача. Другой способ основан на идеях алгебрологического подхода, который был предложен в работе [2]. Этот подход базируется на использовании произвольных ЭК (не обязательно являющихся корректными) и объединяет идеи логического и алгебраического подходов.

Алгебраический подход, развиваемый школой Ю.И. Журавлева, применяется тогда, когда требуется скорректировать работу нескольких распознающих алгоритмов, каждый из которых безошибочно классифицирует лишь часть обучающих объектов [5–7]. Цель коррекции – сделать так, чтобы ошибки одних алгоритмов были скомпенсированы другими алгоритмами и качество результирующего алгоритма оказалось лучше, чем качество каждого из базовых алгоритмов в отдельности. Об алгебрологическом подходе говорят, когда каждый базовый алгоритм однозначно определяется некоторым ЭК и корректирующие функции являются булевыми. Следует отметить, что в ряде работ термин “логический корректор” используется также в случае, когда работа семейства некорректных эвристических процедур классификации корректируется логической функцией (например, см. [7]).

Основным понятием алгебрологического подхода является понятие корректного набора ЭК. Рассмотрим набор ЭК U = {($\sigma$₁, H₁), ..., ($\sigma$_r , H_r)}. Обозначим через $B_{\left({\sigma }_i,H_i\right)}\left(S\right), i = \overline{1, r}$, S ∈M, S = (a₁, ..., a_n), значение, которое принимает конъюнкция $B_{\left({\sigma }_i,H_i\right)}$ на наборе (a₁, ..., a_n). Бинарный вектор $U\left(S\right)=\left\{B_{\left({\sigma }_i,H_i\right)}\left(S\right),...,B_{\left({\sigma }_i,H_i\right)}\left(S\right)\right\}$ – отклик набора U на объекте S. Набор U называется корректным для класса K, если не существует двух прецедентов с одинаковыми откликами на этом наборе и таких, что один из них принадлежит K, а другой не принадлежит K. Корректный для класса K набор ЭК называется тупиковым, если никакое его собственное подмножество не является корректным для класса K набором ЭК.

Нетрудно видеть, что для корректного набора U всегда существует частичная булева функция, выполняющая роль корректирующей функции. Эта функция определена на откликах прецедентов и принимает значение 1, если прецедент из K, и принимает значение 0 в остальных случаях. Особо следует отметить корректные наборы ЭК, имеющие монотонную булеву функцию в качестве корректирующей функции и называемые монотонными. Очевидным является следующее утверждение.

Утверждение 1. Набор ЭК $U=\left\{({\sigma }_1,H_1),...,({\sigma }_r,H_r)\right\}$ – монотонный корректный набор для класса K тогда и только тогда, когда для любых двух обучающих объектов S ′ и S ″ таких, что S ′ ∈ K, S ″ ∉ K, можно указать i в {1, 2, ..., r }, такое, что $B_{({\sigma }_i, H_i)}$(S ′) = 1 и $B_{({\sigma }_i, H_i)}$(S ″) = 0.

Требование монотонности можно убрать, если условие утверждения 1 заменить на условие $B_{\left({\sigma }_i,H_i\right)}\left(S^{\text{'}}\right)\ne B_{\left({\sigma }_i,H_i\right)}\left(S^{\text{'}\text{'}}\right)$.

Модели алгоритмов распознавания, основанные на построении корректных наборов ЭК, получили название логических корректоров.

При распознавании объекта S процедура голосования по корректному набору ЭК U заключается в следующем. Для каждой пары объектов (S, S ′), где S ′ ∈ K, выписываются отклики U(S) и U(S ′) этих объектов на наборе U. Объект S не получает голос за принадлежность классу K, если не выполнено U(S ′)$\le$U(S) (здесь и далее запись U(S ′) $\le$ U(S) означает, что каждая координата вектора U(S ′) не превосходит соответствующую координату вектора U(S)). Если U – монотонный корректный набор ЭК класса K и U(S ′) $\le$ U(S), то объект S получает голос за принадлежность классу K. Если же U не является монотонным корректным набором ЭК класса K, то S получает голос за принадлежность к классу K только в случае U(S ′) = U(S). Решение прикладных задач показало, что монотонный логический корректор работает лучше логического корректора с немонотонной корректирующей функцией.

На этапе построения семейств тупиковых корректных наборов ЭК, а также при построении процедур, основанных на голосовании по тупиковым представительным ЭК, приходится решать сложные дискретные задачи. Труднорешаемость этих задач обусловлена экспоненциальным ростом числа решений с ростом размера задачи и сложностью нахождения каждого нового решения. Одна из основных – монотонная дуализация. Задача допускает несколько формулировок. Ниже приведена ее матричная формулировка [13].

Пусть L – произвольная булева матрица. Набор различных столбцов W матрицы L называется покрытием, если каждая строка матрицы L в пересечении хотя бы с одним из столбцов, входящих в W, даст 1 (т.е. в подматрице матрицы L, образованной столбцами из W, не должно быть строк вида (0,…,0)). Покрытие с минимальным числом столбцов называется минимальным. Покрытие называется неприводимым, если никакое его собственное подмножество не является покрытием. Неприводимость покрытия означает, что в подматрице матрицы L, образованной столбцами набора W, должна быть каждая из строк (1, 0, 0,…, 0, 0), (0, 1, 0,…, 0, 0),…, (0, 0, 0,…, 0, 1). Требуется перечислить все неприводимые покрытия матрицы L. Алгоритмы перечисления неприводимых покрытий булевой матрицы применяются для поиска минимальных покрытий.

Другие формулировки монотонной дуализации используют понятия теории булевых функций (дуализация монотонной конъюнктивной нормальной формы) и понятия теории графов (дуализация гиперграфа) [14]. Задача имеет много важных приложений. Среди алгоритмов монотонной дуализации наиболее эффективны асимптотически оптимальные алгоритмы. Лидирующую позицию занимает алгоритм RUNC-M [13].

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

Прикладные задачи классификации не всегда могут быть описаны в рамках классической постановки логической классификации, когда отдельные значения признака сравниваются с использованием простого отношения равенства. Довольно часто встречаются задачи классификации, в которых каждый признак принимает значения из некоторого частично упорядоченного множества. В работе [8] предложена схема синтеза корректных классических моделей логических алгоритмов распознавания при условии, что на множествах значений целочисленных признаков заданы конечные частичные порядки и признаковые описания изучаемых объектов – элементы декартова произведения заданных порядков. Фактически обобщены базовые понятия, используемые при логическом анализе целочисленных данных в задаче классификации по прецедентам, и приведены условия корректности основных логических процедур классификации. Аналогичным образом могут быть построены и логические корректоры над произведением частичных порядков. В условии содержания ЭК ($\sigma$, H), H = {x_j1, ..., x_jr}, $\sigma$ = ($\sigma$₁, ..., $\sigma$_r), в объекте S, S = (a₁, ..., a_n), следует заменить знак равенства на знак следования. Тогда соответствующее определение будет следующим: ЭК ($\sigma$, H) содержится в объекте S, если a_ji $\le$ s_i при i = $\overline{1, r}$. Остальные введенные выше определения полностью сохраняются. Так же, как и в классическом случае (случае антицепей), для существования корректных наборов ЭК необходимо, чтобы описания объектов из разных классов были несравнимы.

2. Построение монотонных логических корректоров с ЭК ранга 1. Каждый (монотонный) корректный набор ЭК для класса K однозначно соответствует покрытию булевой матрицы L_K, построенной следующим образом по прецедентной информации.

Выпишем всевозможные ЭК, каждый из которых содержится в хотя бы одном обучающем объекте класса K. Пусть это будет множество ЭК {Q₁, ..., Q_u}. Тогда каждой строке в L_K соответствует пара прецедентов S ′ и S ″ таких, что S ′ ∈ K, S ″ ∉ K, а каждому столбцу соответствует один из ЭК Q₁, ..., Q_u. На пересечении строки и столбца, порождаемых парой объектов (S ′, S ″) и ЭК Q_j, j = $\overline{1, u}$, ставится 1, если B_{Q j}(S ′) = 1 и B_{Q j}(S ″) = 0, т.е. Q_j содержится в S ′ и не содержится в S ″, иначе ставится 0. Нетрудно видеть, что набор ЭК является монотонным (тупиковым) корректным набором для K тогда и только тогда, когда соответствующий набор столбцов матрицы L_K является (неприводимым) покрытием.

Как правило, даже для задач небольшой размерности процедура перечисления монотонных тупиковых корректных наборов ЭК (МТК-наборов) для класса K с использованием матрицы L_K требует значительных вычислительных ресурсов, в связи с чем встает вопрос о разработке эффективных методов решения задач алгебрологической коррекции как в общем случае, так и в следующих практически важных случаях: 1) каждый МТК-набор состоит из ЭК ранга 1; 2) в условиях задачи 1 на множестве N_j, j = $\overline{1, u}$, допустимых значений признака x_j задан частичный порядок и считается, что ЭК ($\sigma$, {x_j}) содержится в объекте S, S = (a₁, ..., a_n), если a_j $\le$ $\sigma$. В каждом из перечисленных случаев требуется разработка не только точных, но и приближенных методов решения задачи, что может оказаться необходимым для увеличения скорости ее решения.

Рассмотрим задачу перечисления МТК-наборов для класса K, порождаемых ЭК ранга 1 при условии, что каждое из множеств N_j, j = $\overline{1, u}$, – антицепь, т.е. любые два элемента в N_j несравнимы. Пусть m₁ – число прецедентов класса K, m₂ – число прецедентов не из класса K.

Нетрудно видеть, что в подматрице матрицы L_K = (a_ij), i = $\overline{1,m_1{m}_2}$, j = $\overline{1, 2n}$, образованной сравнением прецедента класса K с прецедентами из других классов, имеется максимум n ненулевых столбцов. Покажем, что указанное свойство матрицы L_K можно использовать для сокращения временных затрат при поиске МТК-наборов для класса K и искомый поиск может быть осуществлен на основе построения специальных наборов столбцов целочисленной матрицы с числом строк, равным числу строк матрицы L_K и с числом столбцов, равным n.

Элементы $a_{i1j1}$ и a_{i2 j2} матрицы L_K назовем совместимыми, если i₁ ≠ i₂, j₁ ≠ j₂, a_{i1 j1} = a_{i2 j2} = 1 и a_{i1 j1} = a_{i2 j2} = 0. Набор U из r единичных элементов матрицы L_K называется совместимым, если выполнено одно и следующих условий: 1) r = 1; 2) r ≥ 2 и любые два элемента набора U совместимы.

Построим матрицу M_K = (b_ij), i = $\overline{1,m_1{m}_2}$, j = $\overline{1, 2n}$, образованную путем сравнения прецедентов класса K с прецедентами из других классов. Каждой строке этой матрицы соответствует пара прецедентов вида (S_i, S_u), где S_i ∈ K, S_u ∉ K. При этом если S_i содержит ЭК ($\sigma$, {x_j}), а S_u не содержит этот ЭК, то в строке, порождаемой парой (S_i, S_u), в столбце с номером j ставится $\sigma +1$, иначе ставится 0.

Элементы b_{i1 j1} и b_{i2 j2} матрицы M_K называются совместимыми, если i₁ ≠ i₂, b_{i1 j1} ≠ 0, b_{i2 j2} ≠ 0 и дополнительно выполнено одно из двух следующих условий: 1) j₁ ≠ j₂ и b_{i2 j1} ≠ b_{i1 j1}, b_{i1 j2} ≠ b_{i2 j2}; 2) j₁ = j₂, b_{i1 j1} ≠ b_{i2 j2}. Набор V из r ненулевых элементов матрицы M_K называется совместимым, если выполнено одно из следующих условий: 1) r = 1; 2) r ≥ 2 и любые два элемента набора V совместимы.

Заметим, что существует взаимно однозначное соответствие между ненулевыми элементами матриц L_K и M_K, при котором каждому единичному элементу e матрицы L_K, расположенному в строке с номером i и столбце, порожденном ЭК ($\sigma$, {x_j}), соответствует элемент $\sigma +1$ матрицы M_K, расположенный в строке с номером i и столбце с номером j, обозначаемый далее П(e).

Утверждение 2. Единичные элементы e₁ и e₂ совместимы в L_K тогда и только тогда, когда элементы П(e₁) и П(e₂) совместимы в M_K.

Доказательство. Пусть e₁ и e₂ – элементы матрицы L_K, такие, что e₁ = e₂ = 1 и элемент e_t, t ∈ (1, 2), расположен в строке с номерами i_t и столбце, порожденном ЭК ($\sigma$_t, {x_jt}). Обозначим через e_{t + 2}, t ∈ (1, 2), элемент в L_K, расположенный в строке с номером i_t и в столбце, порожденном ЭК ($\sigma$, {x_j}), в котором $\sigma$ = $\sigma$₂, j = j₂ при t = 1 и $\sigma = {\sigma }_1$, j = j₁ при t = 2.

I. Пусть элементы e₁ и e₂ совместимы в матрице L_K и элемент e_t, t ∈ (1, 2), расположен в строке с номерами i_t и столбце, порожденном ЭК ($\sigma$, {x_j}). Предположим, что элементы П(e₁) и П(e₂) не совместимы в M_K. Тогда в случае j₁ ≠ j₂ получаем, что хотя бы один из элементов e₃ и e₄ не равен 0. Если же j₁ = j₂, то ${\sigma }_1 = {\sigma }_2$, т.е. элементы e₁ и e₂ расположены в одном и том же столбце матрицы L_K. Таким образом, в обоих случаях возникает противоречие с тем, что e₁ и e₂ совместимые в L_K элементы.

II. Пусть элементы П(e₁), П(e₁) = ${\sigma }_1 + 1$, и П(e₂), П(e₂) = ${\sigma }_2 + 1$, совместимы в матрице M_K и расположены в строках i₁ и i₂ соответственно. Тогда e₁ = e₂ = 1.

Предположим, что элементы e₁ и e₂ не совместимы в L_K и j₁ ≠ j₂. Это означает, что выполнено хотя бы одно из двух равенств e₃ = 1 и e₄ = 1, где e_{t + 2}, t ∈ {1, 2}, – элемент в L_K, расположенный в строке с номером i_t и в столбце, порожденном ЭК ($\sigma$,{x_j}), в котором $\sigma = {\sigma }_2$, j = j₂ при t = 1 и $\sigma = {\sigma }_1$, j = j₁ при t = 2. Если, например, e₃ = 1, то П(e₃) = П(e₂) = $\sigma$₂ + 1. Противоречие с условием совместимости элементов П(e₁) и П(e₂).

Допустим, что элементы e₁ и e₂ не совместимы в L_K и j₁ = j₂ = j. Тогда существует t ∈ (1, 2), такое, что на пересечении строки с номером i_t матрицы L_K со столбцами, порождаемыми ЭК ($\sigma$₁,{x_j}) и ($\sigma$₂,{x_j}), стоит число 1, что недопустимо при $\sigma$₁ ≠ $\sigma$₂. Следовательно, $\sigma$₁ = $\sigma$₂. Противоречие с условием совместимости элементов П(e₁) и П(e₂).

Утверждение 2 доказано.

Пусть $\left\{{\sigma }_1,...,{\sigma }_r\right\}$ – совместимый набор элементов матрицы M_K, в котором $\sigma$_t, – элемент столбца с номером j_t, и пусть H – набор столбцов с номерами j₁, ..., j_r . Через $\tilde{H}$ обозначим набор из всех различных столбцов, встречающихся в H. Будем говорить, что H – $({\sigma }_1, ..., {\sigma }_r) ({\sigma }_1, ..., {\sigma }_r)$ – совместимый набор столбцов. Будем считать, что для H выполнено условие покрываемости, если подматрица $M_K^H$ матрицы M_K, образованная столбцами из $\tilde{H}$, не содержит строк вида (0,…,0). Назовем H корректным ($\sigma$₁, ..., $\sigma$_r) покрытием для M_K, если для H выполнено условие покрываемости. Корректное покрытие матрицы M_K, имеющее наименьшее число столбцов, назовем минимальным. Согласно утверждению 2, существует взаимно однозначное соответствие между множеством корректных покрытий матрицы M_K и множеством неприводимых покрытий матрицы L_K. Следовательно, для синтеза МТК-наборов класса K могут быть применены алгоритмы построения корректных покрытий матрицы M_K, а для синтеза минимальных по мощности МТК-наборов класса K могут быть применены алгоритмы построения минимальных корректных покрытий матрицы M_K.

Для перечисления корректных покрытий матрицы M_K авторами построен алгоритм АЛКОР. Ниже приведена схема работы этого алгоритма.

Предположим, что C(M_K) – множество всех совместимых наборов столбцов матрицы M_K и пусть H ∈ C(M_K). Столбец h матрицы M_K совместим с H, если набор столбцов H ∪ h принадлежит C(M_K), иначе h несовместим с H. Если в матрице M_K не существует столбца, совместимого с H, то H – максимальный совместимый набор столбцов этой матрицы. Допустим, что C ^*(M_K) – множество всех максимальных совместимых наборов столбцов матрицы M_K.

Для наглядности работу алгоритма АЛКОР можно представить в виде обхода дерева решений (ДР) в глубину. Корень ДР – пустой набор, вершина ДР – набор из C(M_K), висячая вершина ДР – набор из C ^*(M_K), которая либо являются корректными покрытием матрицы M_K, найденным впервые, либо соответствует лишнему шагу.

Первоначально матрица M_K рассматривается в качестве текущей матрицы. Построение ДР начинается с вершины, которая порождается некоторым ненулевым столбцом с номером j₁ матрицы M_K и некоторым ненулевым элементом $\sigma$₁ этого столбца. Далее в роли текущей матрицы выступает подматрица матрицы M_K, полученная описанным ниже способом. Для построения дочерней вершины для вершины ($\sigma$₁, j₁) алгоритм по определенному правилу выбирает в текущей матрице ненулевой столбец с номером j₂ и элемент $\sigma$₂ этого столбца, совместимый с элементом $\sigma$₁. Строится новая вершина ($\sigma$₂, j₂). При этом возможно, что j₁ = j₂. После построения очередной вершины ($\sigma$_r, j_r), r ≥ 1, порождаемой ($\sigma$₁, ..., $\sigma$_r)-совместимым набором столбцов H матрицы M_K, текущая матрица изменяется следующим образом. Из нее удаляются все строки, дающие $\sigma$_r в пересечении со столбцом с номером j_r .

Алгоритм АЛКОР применяет “жадную” стратегию выбора столбцов для построения дочерних вершин в ДР. Всякий раз после построения очередной вершины ($\sigma$_r, j_r), r ≥ 1, в новой текущей матрице среди строк с наименьшим числом ненулевых элементов выбирается строка с наименьшим номером. Далее среди столбцов, которые в пересечении с выбранной строкой дают отличные от 0 элементы, ищется столбец с наименьшим номером j_{r + 1}, такой, что ненулевой элемент $\sigma$_{r +1} этого столбца, расположенный в выбранной строке, совместим с текущим совместимым набором {$\sigma$₁, ..., $\sigma$_r} элементов матрицы M_K. Если указанный столбец найти не удается, то вершина ($\sigma$_r , j_r) становится висячей. Далее либо происходит переход к новому шагу путем возврата на более высокий уровень ДР, либо алгоритм заканчивает работу. В противном случае ($\sigma$_r , j_r) – внутренняя вершина ДР, процесс построения текущей ветви дерева продолжается, и строится новая вершина ($\sigma$_{r + 1}, j_{r + 1}). Если можно выбрать только один столбец, обладающий названными выше свойствами, то ($\sigma$_{r + 1}, j_{r + 1}) – концевая вершина.

Пусть висячая вершина ($\sigma$_r , j_r) порождает максимальный ($\sigma$₁, ..., $\sigma$_r)-совместимый набор столбцов H матрицы M_K. В этом случае для H проверяется условие покрываемости. Если условие покрываемости для H выполнено, то множество корректных покрытий матрицы M_K, построенных на предыдущих шагах, пополняется добавлением к нему набора столбцов H, в противном случае это множество не меняется. Алгоритм заканчивает работу, если каждая из вершин ($\sigma$_i, j_i), i = $\overline{1, r}$, является концевой вершиной.

Таким образом, число шагов алгоритма АЛКОР равно числу висячих вершин в ДР. Сложность шага алгоритма O(qm₁m₂ n), q = min(m₁, n).

Схема работы алгоритма АЛКОР близка к схеме работы асимптотически оптимального алгоритма перечисления неприводимых покрытий булевой матрицы RUNC-M [13]. В настоящей работе на базе алгоритмов RUNC-M и АЛКОР построены алгоритмы RUNC-M+ и АЛКОР+, осуществляющие соответственно поиск минимальных покрытий матрицы L_K и минимальных корректных покрытий матрицы M_K . В этих алгоритмах добавлена текущая переменная, фиксирующая минимальное число столбцов в найденных покрытиях.

В случае, когда на каждом множестве N_j, j = $\overline{1, n}$, допустимых значений признака x_j задан частичный порядок, применялся аналогичный подход. Проведены эксперименты, показавшие эффективность предложенной методики решения поставленных задач. В экспериментах при решении реальных задач рассматривался специальный линейный порядок, учитывающий частоту встречаемости значения признака в описаниях прецедентов [16].

3. Результаты экспериментов. Выполнены эксперименты на случайных модельных бинарных данных с равновероятным появлением 0 и 1, с равномощными непересекающимися классами K₁ и K₂, с числом прецедентов m и числом признаков n. В табл. 1 приведено среднее время (по 20 запускам) поиска минимальных покрытий матрицы L_K, K ∈ {K₁, K₂}, алгоритмами RUNC-M+ и АЛКОР+. Время счета указано в секундах. Дополнительно указано среднее число минимальных покрытий q.

 

Таблица 1. Эффективность алгоритмов RUNC-M+ и АЛКОР+ на модельных данных

Номер задачи	Размер задачи		RUNC-M+	АЛКОР+
	m × n
1	20 × 40	76.2	0.9	0.4
2	20 × 60	104.2	6.7	2.6
3	20 × 80	169	24.2	3.6
4	20 × 100	269.4	96.9	10.6
5	20 × 120	861.3	115.1	17.7
6	20 × 140	397	150.9	20.9
7	20 × 160	422.6	137.1	24.7
8	20 × 180	642.8	256.4	42.3
9	20 × 200	1131.3	409.3	61.3

 

Из результатов, представленных в табл. 1, следует, что алгоритм АЛКОР+ работает существенно быстрее алгоритма RUNC-M+ в случае, когда m $\ll$ n. В среднем при n ≥ 100 время счета алгоритма RUNC-M+ в 6.5 раз больше, а при n < 100 – в 3.5 раза. Проведены также аналогичные эксперименты с фиксированным числом признаков, равным 20, и с числом прецедентов, меняющимся от 40 до 200, которые показали, что по времени счета АЛКОР+ незначительно уступает RUNC-M+ (до 1.5 раз).

Выполнены эксперименты на пяти реальных задачах с двумя классами, содержащих как бинарные признаки, так и целочисленные признаки высокой значности. Одна задача (“tic-tac-toe”) была взята из репозитория UCI [17], а остальные – из репозитория ФИЦ ИУ РАН [11]. Тестирование новой модели монотонного логического корректора (МКОР), проводилось с линейными порядками на множествах значений признаков, согласно частоте встречаемости каждого значения [16]. Исходная обучающая выборка 10 раз разбивалась на обучение и контроль в соотношении 80 и 20%. Качество классификации оценивалось двумя функционалами: $Q= ({\tilde{m}}_1+{\tilde{m}}_2)/(m_1+m_2)$ – средняя точность и $Q_b=1/2\left({\tilde{m}}_1/m_1 +{\tilde{m}}_2/m_2\right)$ – сбалансированная точность, где m_i, i ∈ {1, 2}, – число контрольных объектов класса K_i, а ${\tilde{m}}_i$ – число верно классифицированных контрольных объектов класса K_i . Для задачи “tic-tac-toe” указаны результаты счета при поиске всех неприводимых покрытий в L_K, так как в L_K всегда было найдено только одно минимальное покрытие. Результаты счета представлены в табл. 2, в которой указаны также среднее число найденных покрытий q и максимальная значность признака k.

 

Таблица 2. Эффективность алгоритма МКОР на реальных данных

Описание задачи		q	Q/Qb	RUNC-M+	АЛКОР+
Название	m × n (k)
insult	79 × 81 (2)	351.2	0.69/0.55	10467.8	1361.6
tic-tac-toe	958 × 9 (3)	112.8*	0.99/0.99	7.4	5.7
dorovski	33 × 12 (33)	1297.8	0.60/0.60	2086.3	351.9
input	344 × 9 (11)	1220.2	0.95/0.94	60989.4	14538.7
sigapur	58 × 15 (58)	34	0.98/0.99	1.1	0.05

 

Из полученных результатов следует, что алгоритм АЛКОР+ работает быстрее алгоритма RUNC-M+, причем существенно быстрее на задачах с большим числом признаков. Время счета в секундах указано в последних двух столбцах табл. 2.

В табл. 3 приведены результаты сравнения качества алгоритма МКОР с такими известными алгоритмами, как Random Forest (RF), бустинг над решающими деревьями (LADTree), наивный байес (NB), алгоритм голосования по всем тупиковым представительным ЭК (ГТП) и модификация алгоритма ГТП, в которой “голосуют” тупиковые представительные ЭК с небольшим рангом (ГТП+). При счете использовалась авторская реализация алгоритмов ГТП и ГТП+. Алгоритмы RF, LADTree и NB были взяты из системы WEKA [18].

 

Таблица 3. Показатели качества тестируемых классификаторов

Название задачи	МКОР Q/Qb	RF Q/Qb	LADTree Q/Qb	NB Q/Qb	ГТП Q/Qb	ГТП+ Q/Qb
insult	0.69/0.55	0.79/0.55	0.64/0.49	0.76/0.55	0.68/0.50	0.76/0.58
tic-tac-toe	0.99/0.99	0.95/0.93	0.76/0.70	0.64/0.71	0.69/0.56	0.69/0.56
dorovski	0.60/0.60	0.50/0.50	0.63/0. 66	0.57/0.56	0.53/0.53	0.69/0.69
input	0.95/0.94	0.97/0.97	0.96/0.96	0.99/0.99	0.64/0.50	0.64/0.50
sigapur	0.98/0.99	0.97/0.93	0.94/0.94	0.94/0.91	0.82/0.50	0.82/0.50

 

Согласно результатам, представленным в табл. 3, качество алгоритма МКОР сопоставимо с другими тестируемыми классификаторами, а на задачах “tic-tac-toe” и “sigapur” МКОР лидирует. При этом качество МКОР на большинстве задач выше качества ГТП, особенно в случае задач с высокой значностью признаков.

На задаче “insult” проведено исследование стохастического варианта классификатора МКОР (табл. 4). Для каждого из 10 случайных разбиений исходной выборки на обучение и контроль в соотношении 80 и 20% на вход w раз подавался случайный набор из p различных столбцов матрицы M_K. Значение параметра w варьировалось от 20 до 200 с шагом 20 и рассматривалось два значения параметра p, а именно p₁ = 0.2n и p₂ = 0.25n. Для каждых p и w учитывались все найденные минимальные покрытия. В табл. 4 также указано среднее время счета t в миллисекундах и среднее число покрытий q по 10 разбиениям исходной выборки.

 

Таблица 4. Эффективность стохастического варианта алгоритма МКОР на задаче “insult”

w	p = p1			p = p2
	Q/Qbalance	t, мс	q	Q/Qbalance	t, мс	q
20	0.76/0.51	18.1	56	0.80/0.51	230.3	250.2
40	0.81/0.54	17.4	162.7	0.81/0.51	230.9	692.3
60	0.74/0.51	14.3	53.3	0.78/0.48	338.8	588.9
80	0.78/0.53	11.2	131.1	0.79/0.49	465.5	682.5
100	0.78/0.52	22.4	186.8	0.81/0. 49	582.2	1248.5
120	0.78/0.53	17.2	126.5	0.78/0.48	1377.7	1159.1
140	0.78/0.49	26.4	245.2	0.79/0.49	527.2	1378.8
160	0.79/0.51	62.5	244.9	0.81/0. 51	1075.9	1612.3
180	0.79/0.48	33.9	267.4	0.81/0.50	896.4	2553.5
200	0.790/0.50	42.6	237.7	0.81/0.50	1459.9	2454.9

 

Нетрудно видеть, что при p = p₁ стохастический вариант алгоритма МКОР показывает схожие результаты с детерминированным вариантом по функционалу Q_b и лучшие результаты по функционалу Q. Время стохастического поиска существенно меньше (в среднем в 40 тыс. раз). При увеличении w качество стохастического алгоритма немного снижается, при этом увеличивается время счета (в среднем в 3 раза). При увеличении параметра p качество стохастического алгоритма немного снижается по функционалу Q_b, но существенно увеличивается время счета (в среднем в 25 раз).

Таким образом, проведенные эксперименты свидетельствуют о целесообразности применения алгоритма АЛКОР+ для построения монотонного логического корректора с ЭК ранга 1. Установлено, что снижение временных затрат особенно заметно, когда число признаков существенно больше числа обучающих объектов. Показано, что предлагаемый стохастический классификатор не уступает по качеству своему детерминированному варианту и работает на реальных задачах в тысячи раз быстрее.

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

About the authors

I. E. Genrikhov

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences

Email: edjukova@mail.ru
Russian Federation, Moscow

E. V. Djukova

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences

Author for correspondence.
Email: edjukova@mail.ru
Russian Federation, Moscow

References

Supplementary files