O‘zbekiston respublikasi fanlar akademiyasi

Определение. Назовем вектор 


-информативным, если сумма его
компонентов равна 

, т.е. 




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

. 
На основе этих результатов специалистами предметной области были 
разработаны рекомендации по предотвращению аварийных ситуаций в процессе 
эксплуатации комплекса конвейера.