close

Вход

Забыли?

вход по аккаунту

?

Процедура группирования контролируемых параметров в диагностической экспертной системе.

код для вставкиСкачать
p
¦ xij j
УДК 519.237.8
ПРОЦЕДУРА ГРУППИРОВАНИЯ
КОНТРОЛИРУЕМЫХ ПАРАМЕТРОВ
В ДИАГНОСТИЧЕСКОЙ
ЭКСПЕРТНОЙ СИСТЕМЕ
МИНЕНКОВА З.Е.
Описывается комбинированный механизм логического вывода, существенным элементом которого является разбиение всего множества контролируемых
параметров на возможно более независимые подмножества. Эта идея реализуется особой процедурой группирования в специальном пространстве, где ?расстояние? между двумя параметрами ? величина, обратная их коэффициенту корреляции.
При построении диагностических экспертных систем возникает необходимость решения задачи
группирования контролируемых параметров.
1. Постановка задачи группирования
Задача кластеризации состоит в следующем.
Пусть A1 , A2 ,..., An ? набор контролируемых параметров объекта, а k j j ? коэффициент корреля1 2
ции между параметрами с номерами j1 и j2 .
Введем индикатор
x ij , принимающий значение,
i 1
Индикатор
1 2
d 1, j 1 , j 2 Џ 1,2 ,..., n .
xij1 j2 будет равен 1 только тогда, когда
оба параметра будут входить в одну i группу.
Индикатор равен 0, если j1 и j2 не входят в i-ю
группу, кроме того, это ограничение не позволяет
образовать группу из одного элемента.
Полученная задача является минимаксной трехиндексной бипланарной транспортной задачей линейного программирования [1].
В результате реализации описанного алгоритма все
множество контролируемых параметров разбивается на подгруппы. Отметим, что трудности аналитического решения сформированной многоиндексной задачи линейного программирования быстро
растут с увеличением размерности задачи. В связи
с этим рассмотрим приближенный алгоритм ее
решения.
2. Эвристический алгоритм группирования
параметров
Алгоритм является итерационным и содержит подготовительный и основной этапы.
Подготовительный этап.
На этом этапе отыскиваются ?центры группирования? в виде пар параметров.
Введем индикатор
1, ???? ????????? i,j ???????? ????? ?????????????,
равное 1, если параметр j назначен в i-ю группу, и
равное 0 ? в противном случае.
Zij
Тогда естественная постановка задачи группирования имеет вид: найти набор
Тогда может быть сформулирована следующая
xij
arg max min min k j1 j2 xij1 xij2 ,
i
0, ???? ?? ????????.
оптимизационная задача. Найти набор
симизирующий
j1 , j2
удовлетворяющий ограничениям
n
i 1 j 1
p
¦x
ij
1,
j 1, 2,..., n,
i 1
где р ? количество групп.
Данное ограничение указывает на то, что каждый
из параметров может попасть только в одну из
групп.
Полученная задача квадратичного булева программирования легко трансформируется в задачу линейного программирования с использованием преобразования xij1 j2 xij1 xij2 . Ясно, что индикатор xij1 j2
равен 1 только в том случае, когда xij1 xij2 1.
При этом исходная задача преобразуется к виду:
найти набор
x ij1 j2
­
Ѕ
arg max ®min min k j1 j2 x ij1 j2 ѕ,
Ї i j1 j2
ї
удовлетворяющий ограничениям
114
n
¦¦ K ij Z ij
L Z ij
Z ij , мак-
(1)
и удовлетворяющий ограничениям
n
¦ Z ij
1 , i 1,2,..., n ,
(2)
¦ Z ij
1, j
(3)
j 1
n
i 1
Z ij
1,2,..., n ,
Z ji .
(4)
Смысл этой задачи очевиден. В матрице коэффициентов корреляции K
K ij отыскивается n
элементов таких, что сумма соответствующих коэффициентов корреляции максимальна. При этом
ограничения (2), (3) обеспечивают выполнение
естественного требования, чтобы никакая пара из
этих n элементов не лежала в одном столбце или
одной строке, т.е. ни один из параметров не может
быть использован для образования двух или более
центров. Ограничение (4) фиксирует то обстояРИ, 2000, № 3
тельство, что элементы матрицы i, j
соответствуют одной и той же паре.
и
j, i
Предварительно сделаем два замечания. Первое из
них относится к любой задаче линейного программирования и состоит в следующем.
Пусть набор x*j , j 1,2,..., n является решением
задачи максимизации для линейной целевой функции
j 1
n
¦ aij x j
c j ,
j
(9)
1,2,..., n,
cijc
cij d i e j , i 1,2,..., m , j 1,2,..., n .
Тогда
m
n
¦¦ cc x
Lc x
ij ij
i 1 j 1
n
m
n
m
n
¦¦ c x ¦¦ d x ¦¦ e x
ij ij
i 1 j 1
i ij
i 1 j 1
j ij
i 1 j 1
m
n
n
m
i 1
j 1
j 1
i 1
L x ¦ d i ¦ xij ¦ e j ¦ xij
bi , i 1,2,...m ,
(6)
n
¦ ccj x j ,
(7)
1,2,..., n при тех же ограничени-
m
n
i 1
j 1
L x ¦ d i ai ¦ e j b j
где
j 1
ccj
b j , j 1,2,..., n,
выполнено преобразование
m
Тогда, очевидно, этот же набор является одновременно решением задачи минимизации для целевой
функции
где
ях.
¦ xij
xij t 0, i 1,2,..., m, j
(5)
1,2,..., n .
Lc x
ai , i 1,2,..., m,
i 1
j 1
xj t 0, j
¦ xij
j 1
m
при ограничениях
n
(8)
и удовлетворяющий ограничениям
n
¦cjxj
n
i 1 j 1
Полученная задача является задачей булева линейного программирования. Дополнительное ограничение (4) существенно отличает ее от классической
задачи назначения, для точного решения которой
мог бы быть применен известный ?венгерский
метод?. Для решения задачи (1)-(4) используем
приближенный алгоритм.
L X
m
¦¦ cij xij
Lx
(10)
L x c,
c ? константа, не зависящая от набора xij
.
Отсюда следует, что на любом наборе, удовлетворяющем (9), значение целевой функции для преобразованной задачи отличается от значения целевой
функции исходной задачи на константу, определяемую только параметрами преобразования и константами самой задачи, но не набором xij .
Поэтому оптимизирующие наборы этих задач совпадают.
Второе замечание справедливо для задач линейного
программирования типа транспортных и касается
возможности так называемых эквивалентных преобразований задач линейного программирования.
Введем следующие определения.
Перейдем к описанию алгоритма.
Определение 1. Задачи линейного программирования будем называть эквивалентными, если их
оптимизирующие наборы совпадают.
матрицы cijc были неотрицательны. Цель описанных ниже операций состоит в получении в результате эквивалентных преобразований исходной мат-
Определение 2. Преобразование, переводящее задачу линейного программирования в эквивалентную
ей задачу, будем называть эквивалентным.
Покажем, что для задач линейного программирования типа транспортных, в том числе и для задач (1)(5), эквивалентным является преобразование, состоящее в прибавлении по всем элементам какойлибо строки и столбца матрицы cij произвольных
констант.
Действительно, пусть для задачи:
найти
xij
,i
1,2,..., m , j 1,2,..., n ,
Предварительно исходная задача максимизации (1)
трансформируется в некоторую эквивалентную ей
задачу минимизации таким образом, чтобы все
элементы полученной для эквивалентной задачи
рицы
cij
такой матрицы
D , которая содержала
бы n нулей, никакая пара из которых не лежала бы
в одной и той же строке и в одном и том же столбце.
Систему нулевых элементов матрицы, обладающей
тем свойством, что никакая пара из них не лежит
в одной строке или в одном столбце, будем называть
системой независимых нулей. Понятно, что если
система независимых нулей содержит ровно n
элементов (больше, чем n их не может быть по
определению), а остальные элементы матрицы
неотрицательны, то решение задачи минимизации
минимизирующий
LD X
n
n
¦¦ cijc xij
i 1 j 1
РИ, 2000, № 3
115
при удовлетворении (2)-(4) состоит в выборе плана
*
назначения X
xij , единичные компоненты
которого соответствуют нулевым элементам (из
системы независимых нулей) матрицы D , получаемой в результате эквивалентного преобразования.
Действительно, так как нет никакой пары независимых нулей, лежащих в одной строке или столбце,
то такой план удовлетворяет ограничениям (2),(3).
Значение целевой функции LD X на этом плане
равно нулю и в силу неотрицательности элементов
матрицы D не может быть уменьшено.
С другой стороны, так как матрица D была
получена из исходной с помощью эквивалентных
преобразований, то набор X * максимизирует (1).
Процедура эквивалентного преобразования исходной матрицы C выполняется следующим образом.
В каждом столбце матрицы C отыскивается максимальный элемент, т.е.
Aj
max cij , j 1,2,..., n .
i
Далее формируется новая матрица C c cijc по
правилу: каждый элемент cijc равен разности между
максимальным элементом A j соответствующего
столбца исходной матрицы и соответствующим
i, j -м элементом исходной матрицы, т. е.
cijc
i 1,2,..., n , j
max cij cij
i
A j cij t 0 ,
(11)
1,2,..., n .
В результате проведения этой операции получим
матрицу C c с неотрицательными элементами, в
каждом столбце которой имеется по крайней мере
один нуль.
Преобразование (11) является эквивалентным, так
как изменение знака матрицы C не искажает
оптимизирующего набора, так же как и прибавление ко всем элементам одного и того же столбца
одной и той же константы.
Теперь в каждой строке матрицы C c отыскивается
минимальный элемент, который вычитается из
всех элементов соответствующей строки матрицы.
Таким образом, элементы получаемой при этом
матрицы C cc рассчитываются по формуле
cijcc
cijc min cijc
j
cijc d i t 0 ,
(12)
i 1,2,..., n , j 1,2,..., n .
Преобразование (12) также является эквивалентным. В результате его проведения в каждой строке
матрицы образуется, по меньшей мере, один нуль.
В силу ограничения (4) требуемую систему независимых нулей, задающих решение задачи выбора
?центров группирования?, можно выбирать из
любой половины (над главной диагональю или под
ней) полученной симметричной системы нулей.
116
Подготовительный этап завершается формированием множества М, состоящего только из элементов, образующих центры группирования.
Основной этап.
П1. Найти j ђ M такой, что
j, i
arg max min K j , jiA
Mi
Сформировать
M
A 1,2
.
M ‰ j.
Поясним приведенные соотношения.
На этом этапе итерационно осуществляется рациональное подключение каждого из параметров, не
использованных в качестве ?центров группирования?, к одной из сформированных групп. Пусть
параметр j не принадлежит ни одному из ?центров
группирования?. Введем следующие обозначения: ji1
? первый элемент из пары, составляющей i -й
?центр группирования?; ji 2 ? второй элемент из
этой пары. Пусть K j , ji1 ? коэффициент корреляции между
j -м параметром и первым элементом
пары из i -го ?центра группирования?, а K j , j ?
i2
коэффициент корреляции между j -м параметром
и вторым элементом из этой пары. Находим среди
этих коэффициентов минимал ьный -
K j , ji
min K j , jiA . Так поступаем с каждым из ?ценA 1, 2
тров группирования? и в каждом случае находим
минимальный коэффициент корреляции. Теперь
имеем набор минимальных коэффициентов корреляции между j -м параметром и каждым ?центром
группирования?. Затем из всего набора минимальных коэффициентов находим максимальный элемент ? K j , ji Этот максимальный коэффициент и
определит, к какому ?центру группирования? следует отнести данный j параметр. Этот коэффициент корреляции характеризует степень статистической связи между j -м параметром и i -й группой.
П2. Если M z 1,2,..., n , то П1 повторить. В противном случае работа алгоритма завершена.
Таким образом, процедура продолжается, пока в
множестве M не окажутся все контролируемые
параметры, т.е. все параметры будут сгруппированы.
Многочисленные вычислительные эксперименты
показали хорошую работоспособность приведенного эвристического алгоритма кластеризации.
Литература: 1. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.:
Радио и связь, 1982. 239 с.
Поступила в редколлегию
Рецензент: Раскин Л.Г.
Миненкова Злата Евгеньевна, преподаватель Машиностроительного техникума ПГТУ (г.Мариуполь).
Научные интересы: классификация, статистическое
оценивание. Адрес: Украина, 87520, Мариуполь, ул.
Мамина-Сибиряка, 37, кв. 28, тел. (0629)38-69-45.
РИ, 2000, № 3
Документ
Категория
Без категории
Просмотров
3
Размер файла
239 Кб
Теги
диагностическая, экспертная, процедур, группирования, система, контролируемой, параметры
1/--страниц
Пожаловаться на содержимое документа