5.3 Поиск логических закономерностей в данных
Основное требование к математическому аппарату Data Minning заключается не только в эффективности классификаторов, но и в интерпретируемости результатов. Методы поиска логических закономерностей в бинарных матрицах наблюдений (как и в некоторых классических методах многомерного анализа) апеллируют к информации, заключенной не в отдельных признаках, а в различных сочетаниях их значений. Для признаков, измеренных в альтернативных шкалах, их значения \(x_i = 0\) или \(x_i = 1\) рассматриваются как элементарные события, что позволяет сформулировать решающие правила на простом и понятном человеку языке логических высказываний, таких как ЕСЛИ {(событие 1) и (событие 2) и ... и (событие N)} ТО ....
Так, классификация лиц в рассмотренном примере рис. 5.1 может быть произведена, например, с помощью логических высказываний 1 и 2:
ЕСЛИ {(голова овальная) и (есть носогубная складка) и (есть очки) и (есть трубка)} ИЛИ {(глаза круглые) и (лоб без морщин) и (есть борода) и (есть серьга)} ТО ("Патриот")ЕСЛИ {(нос круглый) и (лысый) и (есть усы) и (брови подняты кверху)} ИЛИ {(оттопыренные уши) и (толстые губы) и (нет родинки на щеке) и (есть бабочка)} ТО ("Демократ").
Математическая запись этих правил выглядит следующим образом:
\[[(x_1=0) \wedge (x_6=1) \wedge (x_{11}=1) \wedge (x_{16}=1)] \vee \\ [(x_{4}=1) \wedge (x_{5}=0) \wedge (x_{10}=1) \wedge (x_{15}=1)] \Rightarrow \omega_1\]
\[[(x_3=1) \wedge (x_8=0) \wedge (x_9=1) \wedge (x_{14}=1)] \vee\\ [(x_2=1) \wedge (x_7=1) \wedge (x_{12}=0) \wedge (x_{13}=1)] \Rightarrow \omega_2.\]
Здесь значки \(\vee\) - конъюнкция (“и”), \(\wedge\) - дизъюнкция (“или”), \(\Rightarrow\) - импликация (“если, то”).
Будем использовать логический метод распознавания, известный под названием алгоритм “Кора”, который в свое время широко использовался в геологоразведочных работах и скрининге лекарственных препаратов (Бонгард, 1967; Вайнцвайг, 1973). В детерминистической версии алгоритма обучающая выборка \(\boldsymbol{x}\), предварительно разделенная на два класса (1 и 2), многократно просматривается и из всего множества высказываний выделяются так называемые непротиворечивые логические высказывания \(\mathbf{\Psi}(\boldsymbol{x}, \tau)\), покрывающие все множество примеров. Непротиворечивым высказыванием для каждого класса считается конъюнкция, которая встречается с вероятностью не менее \(\tau\) только в одном классе и ни разу не встречается в другом.
Представленный ниже скрипт выполняет перебор всех возможных комбинаций столбцов \(x_i\), \(i = 1, \dots, m = 16\), по 2, 3 и maxKSize = 4 с использованием функции combn(). Для каждой комбинации столбцов перебираются все возможные варианты событий (x_i = 0 или x_i = 1). Для сокращения объема вычислений подмножества исходной матрицы трансформировались в векторы символьных бинарных переменных, а комбинации значений \(x_i\) выражались наборами “битовых масок” (например, "000", "001", "010", "011", "100", "101", "110", "111").
В ходе перебора конъюнкции, отобранные по совокупности условий, будем сохранять в трех глобальных объектах класса list, для чего используем оператор глобального присваивания <<-. Определим предварительно несколько функций:
# Преобразование числа в набор битов (5 -> "0101")
number2binchar <- function(number, nBits) {
paste(tail(rev(as.numeric(intToBits(number))), nBits),
collapse = "")
}
# Поиск конъюнкций по набору битовых масок
MaskCompare <- function(Nclass, KSize, BitMask,
vec_pos, vec_neg, ColCom) {
nK <- sapply(BitMask, function(x) {
if (sum(x == vec_neg) > 0) return (0)
if (minNum > (countK = sum(x == vec_pos))) return(0)
# Cохранение конъюнкции в трех объектах list
Value.list[[length(Value.list) + 1]] <<-
list(Nclass = Nclass, KSize = KSize,
countK = countK, Bits = x)
ColCom.list[[length(ColCom.list) + 1]] <<- list(ColCom)
RowList.list[[length(RowList.list) + 1]] <<-
list(which(vec_pos %in% x))
return(countK) } )
}Зададим минимальную частоту встречаемости конъюнкций minNum = 4 (т.е. \(\tau\) = 50%) и выполним формирование всех логических правил для рассматриваемого примера:
DFace <- read.delim(file = "data/Faces.txt",
header = TRUE, row.names = 1)
maxKSize <- 4
minNum <- 4
# Списки для хранения результатов
Value.list <- list() # Nclass, KSize, BitMask, countK
ColCom.list <- list() # Наименования переменных ColCom
RowList.list <- list() # Номера индексов строк RowList
# Перебор конъюнкций разной длины
for (KSize in 2:maxKSize) {
BitMask <- sapply(0:(2^KSize - 1),
function(x) number2binchar(x, KSize))
cols <- combn(colnames(DFace[, -17]), KSize)
for (i in 1:ncol(cols)) {
SubArr <- DFace[, (names(DFace) %in% cols[, i])]
vec1 <- apply(SubArr[DFace$Class == 1, ],1,
function(x) paste(x, collapse = ""))
vec2 <- apply(SubArr[DFace$Class == 2,], 1,
function(x) paste(x, collapse = ""))
MaskCompare(1, KSize, BitMask, vec1, vec2, cols[, i])
MaskCompare(2, KSize, BitMask, vec2, vec1, cols[, i])
}
}
# Создание результирующей таблицы
DFval = do.call(rbind.data.frame, Value.list)
nrow = length(Value.list)
DFvar <- as.data.frame(matrix(NA, ncol = maxKSize + 1, nrow = nrow,
dimnames = list(1:nrow, c(
paste("L", 1:maxKSize, sep = ""),
"Объекты:"))))
for (i in 1:nrow) {
Varl <- unlist(ColCom.list[[i]])
DFvar[i, 1:length( Varl)] <- Varl
Objl <- unlist(RowList.list[[i]])
DFvar[i, maxKSize + 1] <- paste(Objl, collapse = " ")
}
DFvar[is.na(DFvar)] <- " "
DFout <- cbind(DFval, DFvar)
# Вывод результатов
print("Конъюнкции класса 1") ## [1] "Конъюнкции класса 1"DFout[DFout$Nclass == 1, ]## Nclass KSize countK Bits L1 L2 L3 L4 Объекты:
## 1 1 2 4 00 x2 x14 2 3 6 8
## 2 1 2 4 00 x3 x7 1 3 5 7
## 7 1 3 4 010 x2 x11 x14 2 3 6 8
## 10 1 3 4 111 x4 x10 x15 2 5 7 8
## 12 1 3 4 111 x6 x9 x11 1 3 6 8
## 13 1 3 4 111 x6 x11 x16 1 3 4 6
## 14 1 3 4 111 x9 x11 x13 1 3 6 8
## 16 1 4 4 0111 x1 x6 x9 x11 1 3 6 8
## 17 1 4 4 0111 x1 x6 x11 x16 1 3 4 6
## 18 1 4 4 0111 x1 x9 x11 x13 1 3 6 8
## 23 1 4 4 1011 x4 x5 x10 x15 2 5 7 8
## 25 1 4 4 1111 x6 x9 x11 x13 1 3 6 8
## 26 1 4 4 0101 x8 x9 x12 x13 1 6 7 8print("Конъюнкции класса 2")## [1] "Конъюнкции класса 2"DFout[DFout$Nclass == 2, ] ## Nclass KSize countK Bits L1 L2 L3 L4 Объекты:
## 3 2 2 4 00 x6 x10 4 5 6 8
## 4 2 2 4 00 x11 x15 1 3 5 7
## 5 2 3 4 111 x2 x4 x7 5 6 7 8
## 6 2 3 4 111 x2 x7 x13 2 5 7 8
## 8 2 3 4 111 x3 x9 x14 1 3 4 6
## 9 2 3 4 111 x4 x7 x16 5 6 7 8
## 11 2 3 4 010 x6 x7 x10 4 5 6 8
## 15 2 4 4 0101 x1 x4 x5 x16 1 6 7 8
## 19 2 4 4 1110 x2 x4 x7 x12 5 6 7 8
## 20 2 4 4 1111 x2 x4 x7 x16 5 6 7 8
## 21 2 4 4 1101 x2 x7 x12 x13 2 5 7 8
## 22 2 4 4 1011 x3 x8 x9 x14 1 3 4 6
## 24 2 4 4 1101 x4 x7 x12 x16 5 6 7 8Результат, содержащий логические высказывания для каждого класса (Nclass) будет выглядеть следующим образом, где KSize - длина коньюнкции, Bits - ее битовая маска, L1-L4 - наименования исходных переменных, countK - встречаемость конъюнкции на объектах своего класса.
Дальнейшая работа с выделенными логическими высказываниями сводится к следующему (реализация алгоритма в R находится в стадии доработки). Из генерируемого списка необходимо исключить подчиненные (или дочерние) конъюнкции, включающие более короткие претенденты: например, для класса 1 высказывание №7 является дочерним по отношению к конъюнкции №1 и должно было быть удалено. После такой операции поглощения ликвидируется избыточность решающего правила, в котором остаются конъюнкции минимального ранга, содержащие выделенные закономерности в концентрированной форме.
Хорошим правилом было бы также исключить высказывания, которые по определенным критериям считаются “предрассудками”. К ним относятся конъюнкции, не связанные с объективным правилом классификации, но, в силу ограниченности выборки, получившие хорошие оценки на обучении. Для выделения признаков, склонных к предрассудкам, выполняют бутстреп-процедуру, в которой обучающая выборка многократно случайным образом разбивается на классы. Разбитая таким образом выборка является тестом, позволяющим присвоить каждому исходному признаку штрафные баллы за склонность к предрассудкам. Конъюнкции, набравшие сверхнормативное количество штрафных очков, из решающего правила исключаются.
Описанием каждого класса является логическая сумма (дизъюнкция) некоторого количества непротиворечивых и продуктивных конъюнкций, прошедших описанные выше этапы отбора. Комбинация этих логических высказываний представляет собой своеобразную мозаично-фрагментарную разделяющую поверхность специального типа (в отличии, например, от линейной плоскости логита). Более общая версия алгоритма “Кора” предполагает выделение логических закономерностей для \(K\) классов, \(K > 2\). Среди конъюнкций выделяются те, которые верны на обучающей выборке чаще, чем некоторый порог \(\tau_1\), для одного из классов и не характерны для любого другого (верны реже, чем в доле случаев \(\tau_2\)).
Существует возможность использовать сгенерированные конъюнкции для экзамена тестируемых примеров по принципу голосования. Чтобы классифицировать новое наблюдение \(\boldsymbol{x}\), подсчитывается число отобранных конъюнкций \(L_k\), характерных для каждого \(k\)-гo класса, которые верны для тестируемого бинарного вектора. Если \(L_k\) является максимальным из всех, то принимается решение о принадлежности объекта \(k\)-му классу.
Алгоритм “Кора”, как и другие логические методы распознавания образов, является достаточно трудоемким, поскольку при отборе конъюнкций необходим полный или частично направленный перебор. Здесь может быть полезно использование процедур эволюционного поиска: генетический алгоритм (genetic algorithm), случайный поиск с адаптацией (СПА - см. книгу Г. С. Лбова, 1981 на сайте math.nsc.ru) и др.