Определение. Назовем вектор
-информативным, если сумма его
компонентов равна
, т.е.
N
i
i
1
.
Для каждой подсистемы, заданной
-информативным вектором
,
определено свое
-мерное признаковое подпространство. В каждое из этих
подпространств введем евклидову норму относительно усечения по
N
j
j
j
x
x
1
2
.
Обозначим
r
p
x
m
x
p
m
i
pi
p
p
,
1
,
1
1
,
где
p
x
усредненный объект класса
p
X
.
Введем функцию
p
m
i
p
pi
p
p
x
x
m
S
1
2
1
.
Функция
p
S
характеризует средний разброс объектов класса
p
X
в
подмножестве признаков, заданных вектором
. Зададим критерий
информативности подсистем в виде функционала
2
,
1
2
1
r
p
q
p q
r
p
p
x
x
I
S
.
(3)
Обозначим
N
N
b
b
b
b
a
a
a
a
...,
,
,
;
...,
,
,
2
1
2
1
,
6
.
,
1
,
1
;
,
1
,
1
1
2
1
,
2
N
j
x
x
m
b
N
j
x
x
a
r
p
m
i
j
p
j
pi
p
j
r
q
p
j
q
j
p
j
p
Тогда функционал (3) сводится к виду
,
,
,
a
I
b
(4)
где (*,*)
скалярное произведение векторов.
Коэффициенты
j
j
b
a ,
не зависят от
и вычисляются заранее. Для
расчета функционала
I
при каждом
требуется порядка N операций.
Рассмотрим оптимизационную задачу
,
max,
,
,
0,1 ,
1,
,
,
,
0,
0,
1,
,
l
i
a
I
b
i
N
N
a b
R
a
b
i
N
i
i
(5)
где
l
является - мерным информативным пространством признаков:
1
0,1 ,
1,
,
N
l
i
i
i
i
N
l
.
Для решения задачи (5) введем вектор-функцию
,
,
a b
b a
,
(6)
которая указывает направление наискорейшего роста функционала
I
в точке
.
Теорема 1. Если
и
- два -информативных вектора и
0,
1,
j
b
j
N
, то
I
I
тогда и только тогда, когда
,
0
.
Введем оператор (следования)
:
такой, при котором
,
max
,
.
Оператор
имеет очевидное конструктивное представление. Если
упорядочить компоненты вектора
, т.е. найти набор попарно различных
индексов
1
2
,
,...,
N
j j
j
таких, при которых
1
2
...
N
j
j
j
, то компоненты
вектора
будут определены как
1
2
1
2
1,
1,...,
1,
0,
0,...,
0
N
j
j
j
j
j
j
.
Иначе говоря, компоненты вектора
, соответствующие первым -
максимальным компонентам вектора
, равны единице, остальные - нулю.
Очевидно, что
также является -информативным вектором, причем
,
max
,
.
(7)
7
Свойство 1. Для произвольного
верно
,
0
.
Из приведенных теоремы 1 и свойства 1 вытекает основное следствие
,
I
I
.
Теорема 2. Если
I
I
, то
max
I
I
.
Заметим, что теорема 2 гарантирует оптимальность полученного решения,
т.е. значение функционала
I
при найденном решении
достигает своего
максимума на множестве
.
На теоремах 1 и 2 основан предлагаемый метод, который реализуется в
виде итеративной процедуры. Причем на первом шаге выбирается произвольный
-информативный вектор
, например,
1,1,...,1,0,0,...,0
. Далее на каждой
итерации новый вектор
определяется из предыдущего с помощью оператора
следования
, т.е. попросту производится присваивание
.
Итерационный процесс продолжается до тех пор, пока функционал
I
растет. В
случае, если рост прекращается, т.е.
I
I
, то
- оптимальное решение.
Обычно это решение достигается, как показали эксперименты, на 3-4 шаге.
Сформулируем рассматриваемый метод в виде алгоритма:
Шаг 1. Входными параметрами являются значения: - требуемое число
признаков; N - количество признаков; a и b - N-мерные векторы.
Шаг 2. Задание вектора
1,1,...,1,0,0,...,0
N
.
Шаг 3. Вычисление значения функционала
I
.
Шаг 4. Вычисление
0
(компоненты вектора
определяются в
виде отдельного блока).
Шаг 5. Вычисление значения функционала
0
0
I
I
.
Шаг 6. Сравнение
0
I
I
. Если неравенство выполняется, то полагаем
0
0
, I
I
и переходим к шагу 4. В противном случае процедура
заканчивается и
- оптимальное значение.
Шаг 7. Выходные параметры:
, I
.
Блок вычисления
0
предусматривает следующие последовательные
операции:
Шаг 1. Входные параметры:
, ,
, ,
N a b
.
Шаг 2. Вычисление вектора
,
,
a b
b a
.
Шаг 3. Задание
0,0,...,0 ,
1
k
.
Шаг 4. Задание
60
max
10
,
1
i
.
Шаг 5. Проверка i-компоненты вектора
. Если
0
i
, то переход к
последующему шагу, иначе - к шагу 8.
Шаг 6. Проверка i-компоненты векторов
max
,
. При
max
переход к
последующему шагу, иначе – к шагу 8.
Шаг 7. Присваивание
max
,
i
m
i
.
Шаг 8.
1
i
i
.
8
Шаг 9. Если
i
N
, то переход к шагу 5. В противном случае переход к
последнему шагу.
Шаг 10. Присваивание
1,
1
m
k
k
.
Шаг 11. Если
k
, то переход к шагу 4, иначе
0
и процедура
заканчивается.
В заключение отметим, что полученные результаты распространяются на
все критерии информативности признаков, заданные функционалами, которые в
принципе можно свести к виду (4).
Предположим, что компоненты вектора a положительны, а вектора b
строго больше нуля, т.е.
1
2
1
2
,
,...,
;
0,
,
,...,
;
0,
1,
N
j
N
j
a
a a
a
a
b
b b
b
b
j
N
,
а также
1
2
1
2
...
N
N
a
a
a
b
b
b
.
(8)
На множестве
рассмотрим задачу (5).
Из определения множества -информативных векторов
следует, что
мощность рассматриваемого множества равна
N
C
. Отсюда вытекает, что для
нахождения максимального значения функционала
I
для заданного
с
применением метода полного перебора [8] вычисления производятся
N
C
раз.
Отсюда имеем, что при каждом заданном существует -информативный вектор
, обеспечивающий
max
I
,
(9)
где
1, N
.
Относительно функции
I
,
1, N
известен результат, которым
воспользуемся в дальнейшем.
Для всех
1, N
в значениях функционала
I
участвуют числа
1
a
и
1
b
[8], т.е., если в качестве исходных данных используются неравенства (8), то у
-оптимального вектора первая координата равна единица.
Воспользовавшись этим результатом, для решения задачи (5), можно
предложить метод перебора, согласно которому максимум функции
I
отыскивается по всем
1
2
,
,...,
N
,
0,1
k
, для которых
1
N
k
k
.
Для организации эффективного перебора строго упорядочим все
возможные
-информативные векторы
. Первым в данном порядке будем
считать вектор, имеющий первые компонент, равные единице, остальные -
нулю. А у последнего вектора последние компонент равны единице, остальные
- нулю.
Пусть задан некоторый
-информативный вектор
1
2
,
,...,
N
r
r
r
r
,
находящийся в определенном месте рассматриваемого порядка. Определяем
правило выбора непосредственно следующего вслед за ним вектора
1
2
1
1
1
1
,
,...,
N
r
r
r
r
.
Если
1
2
1
2
3
*,
*,...,
*,
1,
0,
0,...,
0
k
k
k
k
N
r
r
r
r
r
r
r
,
то
1
1
2
2
1
2
3
3
1
1
1
1
1
1
1
,
,...,
,
0,
1,
,...,
k
k
k
k
k
k
N
N
r
r
r
r
r
r
r
r
r
r
r
r
.
Если
1
2
1
2
1
1,
1,...,
1,
0,
0,...,
0,
1,...,
1
k
k
k
j
j
N
r
r
r
r
r
r
r
r
,
то
9
1
1
2
2
1
1
1
2
1
1
1
1
1
1
2
1
1
,
,...,
,
1,
1,...,
1,
0,...,
0
k
k
k
k
r
r
r
r
r
r
r
r
k N
j
k N
j
N
r
r
r
.
Здесь знак «*» обозначает «ноль» или «единица».
Схематично это правило представим в виде
.
В работе [8] доказано, что приведенное правило гарантирует перебор всех
возможных вариантов, начиная с первого и кончая последним.
Принцип работы этого алгоритма используем для решения задачи (1).
Только в данном случае в качестве последнего вектора
примем вектор
0,1,1,...1,0,0,...,0
, а не
0,0,...,0, 1,1,...1
.
Количество вычислений функционала
I
в данном методе для заданного
2
равно
1
1
1
1
1 !
!
! !
1 ! !
!
i
i
N
N
П N
i
П N
i
N
N
C
C
N
N
1
1
!
i
П N
i
.
Предложенный алгоритм дает оптимальный результат для решения задачи
(1), причем число итераций вычисления функционала в данном методе
существенно меньше, чем в методе полного перебора [8].
Из результатов предложенной схемы нетрудно сформулировать простой
алгоритм максимизации критерия информативности подсистем признаков
методом частичного перебора. Этот алгоритм реализуется следующим образом:
Шаг 1. Полагаем
1,1,...1,0,0,...,0
.
Шаг 2. Вычисление
I
.
Шаг 3. Полагаем
max
max
,
I
I
.
Шаг 4. Определение
Q
(по правилу следования).
Шаг 5. Вычисление
I
.
Шаг 6. Проверка: если
max
I
I
, то присваиваем
max
max
,
I
I
. В
противном случае осуществляется непосредственный переход к следующему
шагу.
Шаг 7. Проверка: если
0,1,1,...1,0,0,...,0
, то процедура заканчивается и
max
задает наилучшую подсистему признаков. Иначе – переход к шагу 4.
Предложенные алгоритмы были апробированы на примерах решения ряда
практических задач, одна из которых связано с оценкой эксплуатационного
состояния
круто
наклонного
конвейера,
установленного
в
карьере
горнометаллургического комбината.
Данный конвейер, может находится в одном из трех состояний: опасное,
предаварийное, безопасное. Сигналы, характеризующие опасное состояние
комплекса, представляли собой первый класс объектов
1
(
)
K
, сигналы,
характеризующие предаварийное состояние - второй класс объектов
2
(
)
K
,
1
...,
,
1
,
1
,
0
...,
,
0
,
0
,
1
*,
...,
*,
*,
,
0
...,
,
0
,
0
,
1
...*,
*,
*,
10
сигналы, характеризующие безопасное состояние - третий класс объектов
3
(
)
K
.
Число признаков, характеризующих каждый объект, было равно 9.
Каждый класс содержит одинаковое число объектов, равное 5056. Таким
образом, каждый объект можно представить в виде вектора
1
2
9
, , ... ,
ij
ij
ij
ij
x
x
x
x
,
где
k
ij
x - k
ый признак j
го объекта
i
го класса, где
1,9;
1,5056;
1,3
k
j
i
.
Задача определения основных показателей, характеризующих состояния
конвейера,
сводилась к решению оптимизационной задачи
,
,
,
.
a
I
opt
b
После определения -информативных наборов признаков (
1,9
) была
решена задача распознавания с использованием метода “ k-ближайших соседей”,
что позволило оценить степень «полезности» каждого из этих наборов признаков
с точки зрения их влияния на качество распознавания объектов контрольной
выборки.
В результате решения этой задачи был определен наиболее
информативный набор признаков
2
5
8
,
,
x x x
, где
2
5
,
x x
и
8
x
представляют значения
сигналов, поступающих от вертикальных компонент трехкомпонентных датчиков
,
1,3
i
D i
.
На основе этих результатов специалистами предметной области были
разработаны рекомендации по предотвращению аварийных ситуаций в процессе
эксплуатации комплекса конвейера.
Do'stlaringiz bilan baham: |